找出数组中数字对之间最小差的最快算法是什么

Question

可能重复：
有可能找到两个在O(n(时间中差值最小的数字吗

例如，在[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

这里有一个类似的问题-是否可以找到在O(n(时间内差值最小的两个数字。它看起来是O(nlogn(。

这个页面也可以提供有用的背景信息。