配列内の数字の対の最小の差異を見つける最速のアルゴリズムは何ですか？

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の背景情報も表示されます。