찾기 쌍 예컨대 ABS (V는 [I] -v은 [J]가)

Question

우리 5 개 요소 int 배열이 있다고 가정하자 최소화되도록 : 5

무엇을 1, 2, 3, 4 내가해야 할 것은 배열의 요소 '뺄셈의 최소 복근 값을 찾는 것이다

우리는 그

1-2 2-3 3-4 4-5 

1-3 2-4 3-5 

1-4 2-5 

1-5 

처럼 확인하고 이러한 뺄셈의 최소 복근 값을 찾아야합니다. 우리는 2 for으로 찾을 수 있습니다. 질문은 하나만 가지고 가치를 찾는 알고리즘이 있습니까 for?

Answer 1

종류의 목록 및 빼기 가까운 두 개의 요소

Answer 2

당신이 목록이 정렬 알고하지 않는 한, 당신은 두

Answer 3

이

 keep 2 variable "minpos and maxpos " and " minneg" and "maxneg" 
     check for the sign of the value you encounter and store maximum positive in maxpos 
     and minimum +ve number in "minpos" do the same by checking in if case for number 
     less than zero. Now take the difference of maxpos-minpos in one variable and 
     maxneg and minneg in one variable and print the larger of the two . You will get 
     desired. 

내가 you definitely know how to find max and min in one for loop를 for 루프에서 그것의 단순 반복 처리를 생각해야합니다

correction :- The above one is to find max difference in case of minimum you need to 
      take max and second max instead of max and min :) 

Answer 4

문제는 sortin과 같습니다. 지. 모든 정렬 알고리즘을 사용할 수 있으며 마지막에는 가장 가까운 요소 간의 차이점을 반환합니다. 데이터에 대한 최종 패스를 사용하여 차이점을 찾거나 정렬 중에 유지할 수 있습니다. 데이터가 정렬되기 전에 인접 요소 간의 최소 차이가 상한이됩니다.

두 개의 루프없이 수행하려면 두 개의 루프가없는 정렬 알고리즘을 사용하십시오. 어떤 의미에서는 의미론처럼 느껴지지만 재귀 정렬 알고리즘은 하나의 루프만으로이를 수행합니다. 이 문제가 단순한 두 루프의 경우에 필요한 n (n + 1)/2 빼기라면 O (n log n) 알고리즘을 사용할 수 있습니다.

Answer 5

최상의 성능을 나타내는 최적의 솔루션은 상수 요소까지 linear O (n)입니다.

이것은 배열에있는 요소의 수에 비례하는 시간을 의미합니다 (물론 적어도 배열의 모든 요소를 ​​읽어야하므로 가장 좋은 방법입니다. 이미 O (n) 시각).

int mindiff(const vector<int>& v) 
{ 
    IntRadixSort(v.begin(), v.end()); 

    int best = MAX_INT; 

    for (int i = 0; i < v.size()-1; i++) 
    { 
     int diff = abs(v[i]-v[i+1]); 
     if (diff < best) 
      best = diff; 
    } 

    return best; 
} 

IntRadixSort 선형 시간 고정 폭 정수 정렬이다 : 여기

은 (리스트가 현재 위치에서 변형 될 수있는 경우도 O (1) 공간을 사용) 이러한 하나의 O (n)이 해결책 알고리즘은 여기서 정의 :

http://en.wikipedia.org/wiki/Radix_sort

개념은 비트 위치에 고정 패스의 일련의를 분할하는 것으로하여 int 치의 고정 비트 너비 특성을 활용할 수 있다는 점이다. 즉, 하이 비트 (32 비트)에서 파티션을 나누고 그 다음으로 높은 비트 (31 비트), 다음 비트 (30 비트) 등을 파티션합니다.

Answer 6

이 도움이 될 수 있습니다

end=4; 
subtractmin; 
m=0; 
for(i=1;i<end;i++){ 
if(abs(a[m]-a[i+m])<subtractmin) 
subtractmin=abs(a[m]-a[i+m];} 
if(m<4){ 
m=m+1 
end=end-1; 
i=m+2; 
}}