배열에서 숫자 쌍 간의 최소 차이를 찾는 가장 빠른 알고리즘은 무엇입니까?

Question

가능한 중복은 :
Is it possible to find two numbers whose difference is minimum in O(n) time

예를 들어

, [4, 2, 7, 11, 8]에서, 알고리즘은 abs(7-8) = 1을 반환해야합니다.

무차별 방식은 O (n)이며 정렬은 O (nlogn)이됩니다. 더 효율적인 방법이 있습니까?

감사

Answer 1

나는 정렬과 비교가 최선의 방법이라고 생각합니다. 예 :

function minDiff(arr) { 
    var min, 
     temp, 
     initDiff = false, 
     arr = arr.sort(function(a, b){return a-b}), 
     last = arr.length - 1, 
     i; 

    for (i = 0; i < last; i++) { 

     if (!initDiff) {    
      min = arr[i + 1] - arr[i]; 
      initDiff = true; 
     } else {    
      temp = arr[i + 1] - arr[i]; 

      if (temp < min) {    
       min = temp;    
      }    
     } 
    } 

    return min; 
} 

var myArr = [ 1, 8, 5, 96, 20, 47 ], 
    min = minDiff(myArr); 

console.log(min); // 3 

Answer 2

여기에 비슷한 질문 - Is it possible to find two numbers whose difference is minimum in O(n) time. O (nlogn) 인 것으로 보입니다.

이 페이지는 useful 배경 정보를 제공 할 수도 있습니다.