performance - 在排序列表中查找具有特定差异的数字

Question

给定 N 个已排序的数字，如果存在一对，我们需要找到差K。

一种O(N log N)解决方案是检查每个数字，使用二分搜索x检查 ( x + K) 是否存在。

我想知道是否有更好的O(n)时间和 O(1) 空间解决方案。

Answer 1

鉴于列表已排序，您可以在 O(n) 时间内通过列表运行两个指针。基本上是这样的：

index1 = 0
index2 = 0
while index2 < size(array):
    if array[index2] - array[index1] == K:
        print both numbers and exit
    if array[index2] - array[index1] < K:
        index2++;
    else
        index1++;

换句话说，如果数字之间的差异太小，则增加较高的数字（使差异更大），否则增加较低的数字（使差异更小）。

您可以通过以下 Python 程序看到这一点：

lst = [1,2,3,4,5,6,7,50,100,120,121,122,123,130,199,299,399]
diff = 7
ix1 = 0
ix2 = 0
while ix2 < len (lst):
    print "Comparing [%d]=%d against [%d]=%d"%(ix1,lst[ix1],ix2,lst[ix2])
    if lst[ix2] - lst[ix1] == diff:
        print lst[ix1], lst[ix2]
        break
    if lst[ix2] - lst[ix1] < diff:
        ix2 = ix2 + 1
    else:
        ix1 = ix1 + 1

输出：

Comparing [0]=1 against [0]=1
Comparing [0]=1 against [1]=2
Comparing [0]=1 against [2]=3
Comparing [0]=1 against [3]=4
Comparing [0]=1 against [4]=5
Comparing [0]=1 against [5]=6
Comparing [0]=1 against [6]=7
Comparing [0]=1 against [7]=50
Comparing [1]=2 against [7]=50
Comparing [2]=3 against [7]=50
Comparing [3]=4 against [7]=50
Comparing [4]=5 against [7]=50
Comparing [5]=6 against [7]=50
Comparing [6]=7 against [7]=50
Comparing [7]=50 against [7]=50
Comparing [7]=50 against [8]=100
Comparing [8]=100 against [8]=100
Comparing [8]=100 against [9]=120
Comparing [9]=120 against [9]=120
Comparing [9]=120 against [10]=121
Comparing [9]=120 against [11]=122
Comparing [9]=120 against [12]=123
Comparing [9]=120 against [13]=130
Comparing [10]=121 against [13]=130
Comparing [11]=122 against [13]=130
Comparing [12]=123 against [13]=130
123 130