在排序列表查找具有特定的差异数 [英] Find numbers having a particular difference within a sorted list

问题描述

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

Given N sorted numbers, we need to find, if there exists a pair, with difference K.

A O（N日志N）的解决办法是检查每个数字 X ，检查（ X +氏/ code>）存在使用的的二进制搜索的。

A O(N log N) solution is to check for every number x , check if (x + K) exists using binary search.

我在想，如果有更好的， O（N）的时间，并为它O（1）空间的解决方案。

I was wondering if there is a better, O(n)time, and O(1) space solution for it.

推荐答案

由于列表进行排序，您可以通过列表中的O（n）时间运行两个三分球。基本上东西线沿线的：

Given the list is sorted, you can run two pointers through the list in O(n) time. Basically something along the lines of:

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++;

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

In other words, if the difference between the numbers is too low, increase the higher number (make difference larger), otherwise increase the lower number (make difference smaller).

您可以看到这个动作有以下Python程序：

You can see this in action with the following Python program:

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

这篇关于在排序列表查找具有特定的差异数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！