在一个数组中寻找最小差值的最快算法是什么？

Question

可能是重复问题：
是否有可能在O(n)时间内找到差值最小的两个数字

例如，在[4，2，7，11，8]中，该算法应返回abs(7-8) = 1。

暴力法将是O(n ²)，排序将给出O(nlogn)。是否有更有效的方法？

谢谢

- javaMan

---

如果数值是整数且范围固定，可以使用基数排序（radix sort）以O(n)的时间进行排序。 - templatetypedef

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

- jbyrd

---

那么...这里的复杂度是什么，你认为它能变得更好吗（比O(nlogn)更优）？这是提问者的问题。 - sehe

Answer 2

这里有一个类似的问题 - 是否可能以O（n）时间找到差最小的两个数。看起来是O（nlogn）。

这个页面也许会提供有用的背景信息，请参考。

- Caffeinated

---

回答太糟糕了 :(. 元素唯一性问题很麻烦。哈希哈希哈希! - Rob Neuhaus

嗯，好的，为什么元素唯一性是个问题？你说的“哈希”是指什么？顺便问一下，你最喜欢的编程语言是什么？ :) - Caffeinated