arrays - 在数组中查找条件最小差异的算法

Question

假设你有一个不同整数的数组： A=[a1,a2,a3,a4,a5...] 我需要找到数组的两个元素，比如 A[i] 和 A[j] 使得 i 更小比 j 和 A[j]-A[i] 是最小的。

以下是有效的解决方案吗？

1. 首先对数组进行排序并跟踪每个元素的原始索引（即：原始（未排序）数组中元素的索引。
2. 遍历排序数组并计算任何两个连续元素之间的差异，以验证较大元素的原始索引大于较小元素的原始索引的初始条件。
3. 答案将是所有这些差异的最小值。

以下是这在示例中的工作方式：

A=[0,-5,10,1]  (in this case the result should be 1 coming from the difference between      A[3] and A[0])
sort A : newA=[-5,0,1,10]
since OriginalIndex(-5)>OriginalIndex(0), do not compute the difference
since OriginalIndex(1)>OriginalIndex(0),we compute the difference =1
since OriginalIndex(10)>OriginalIndex(1), we compute the difference =9
The result is the minimal difference, which is 1

Answer 1

如果您要找到的是正的最小差异，那么基本上，您的问题是：

Find two closest elements in an array.

O(nlogn) 解决方案很简单：

1. 排序——O(nlogn)
2. 获取两个相邻元素之间的差异并找到最小的 - O(n)

所以整体运行时间是O(nlogn)

您不必关心索引。因为你是什么都abs(A[i]-A[j])=abs(A[j]-A[i])无所谓i>jj>i

Answer 2

这是一种解决方案，时间上为 O(n^2)，空间上为 O(1)。在伪代码中：

for i = 0; i < array.length; i++
    for j = i + 1; j < array.length; j++
        if a[j] - a[i] < min
            min = a[j] - a[i]
return min