高效的方式來找到一個數組中的最小差異對

我想解決一個問題，需要我找到一個數組中的最小差異對。高效的方式來找到一個數組中的最小差異對

例如，如果陣列是

6,7,1,3,9

輸出是

(6,7)

具有1差是最小的。

我能想出的最快解決方案是對數組進行排序並遍歷排序後的數組，以找到最小差異[O（nlogn）]。有沒有一種方法來優化或更好地解決O（n）或O（logn）？

編輯：數組的所有元素都是不同的。

來源

2017-09-24 penguin

數組是否始終是離散的和獨特的？即你會得到[1,2,3,2]還是[1,2,1.5,1.56]？ –

是的。所有元素都是不同的。 – penguin

如果是這樣，你至少可以在第一次的差異處停止迭代。這就是我目前所掌握的。 –

假設所有的數字都是獨特和分泌，你可以停止搜索一次所不同的是1

也有這個問題，維基百科的文章在這裏：https://en.wikipedia.org/wiki/Closest_pair_of_points_problem

另外一個問題在這裏：Finding out the minimum difference between elements in an arrays

我的進步：

int[] a = new int[] {4, 9, 1, 32, 13}; 
Arrays.sort(a); 
int minDiff = a[1]-a[0]; 
for (int i = 2 ; i != a.length ; i++) { 
    minDiff = Math.min(minDiff, a[i]-a[i-1]); 
    if (minDif == 1) 
     break; 
} 
System.out.println(minDiff);

來源

2017-09-24 07:44:43

我不指望你能找到一個O(log n)解決方案，因爲至少需要遍歷整個數組以查看其元素。對我來說，排序方法似乎是最優的，但是如果你的數字來自之前已知的不太大的集合（例如，對於一些非常小的N，來自範圍[0; N]的整數），則有可能提高複雜性。在這種情況下，您可以使用最差情況下的複雜度爲O(n + N)的計數排序算法。但請注意，空間使用量也是O(n + N)。計數排序有很多來源，這一個應該足夠了：https://en.wikipedia.org/wiki/Counting_sort

來源

2017-09-24 07:48:46 Ardavel

您試圖解決Closest Pair問題，其中您搜索數據集中距離彼此最小的兩個點。將維度設置爲1會減少您的情況（一個點只是一個數字）。

的算法有效地解決這一問題的時間複雜度爲：

O（nlogn）

注意，分治技術可在此上下文中使用。例如在這些slides中。提示：如果您認爲數據點是截然不同的，那麼當您找到距離1（因爲它不能小於1）時，您可以停止算法，但這可能不會是這種情況你的數據。

來源

2017-09-24 08:11:11 gsamaras

高效的方式來找到一個數組中的最小差異對

回答

相關問題