什麼是最快的算法來找到數組中的成對數之間的最小差異？

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背景信息。