高效的方式来找到一个数组中的最小差异对

Question

我想解决一个问题，需要我找到一个数组中的最小差异对。

例如，如果阵列是

6,7,1,3,9 

输出是

(6,7) 

具有1差是最小的。

我能想出的最快解决方案是对数组进行排序并遍历排序后的数组，以找到最小差异[O（nlogn）]。有没有一种方法来优化或更好地解决O（n）或O（logn）？

编辑：数组的所有元素都是不同的。

Answer 1

假设所有的数字都是独特和分泌，你可以停止搜索一次所不同的是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); 

Answer 2

我不指望你能找到一个O(log n)解决方案，因为至少需要遍历整个数组以查看其元素。对我来说，排序方法似乎是最优的，但是如果你的数字来自之前已知的不太大的集合（例如，对于一些非常小的N，来自范围[0; N]的整数），则有可能提高复杂性。在这种情况下，您可以使用最差情况下的复杂度为O(n + N)的计数排序算法。但请注意，空间使用量也是O(n + N)。计数排序有很多来源，这一个应该足够了：https://en.wikipedia.org/wiki/Counting_sort

Answer 3

您试图解决Closest Pair问题，其中您搜索数据集中距离彼此最小的两个点。将维度设置为1会减少您的情况（一个点只是一个数字）。

的算法有效地解决这一问题的时间复杂度为：

O（nlogn）

注意，分治技术可在此上下文中使用。例如在这些slides中。提示：如果您认为数据点是截然不同的，那么当您找到距离1（因为它不能小于1）时，您可以停止算法，但这可能不会是这种情况你的数据。