使用排序查找列表中最接近的两个数字

Question

如果我得到一个 integers/floats 的列表，我如何使用排序找到最接近的两个数字？

Answer 1

可能不止一种可能。考虑这个列表

[0,1, 20, 25, 30, 200, 201]

[0,1] 和 [200, 201] 相等最接近。

Answer 2

这样的方法会如你所愿：

>>> def minDistance(lst):
    lst = sorted(lst)
    index = -1
    distance = max(lst) - min(lst)
    for i in range(len(lst)-1):
        if lst[i+1] - lst[i] < distance:
            distance = lst[i+1] - lst[i] 
            index = i
    for i in range(len(lst)-1):
        if lst[i+1] - lst[i] == distance:
            print lst[i],lst[i+1]

在第一个 for 循环中我们找到最小距离，在第二个循环中，我们打印所有具有这个距离的对。工作原理如下：

>>> lst = (1,2,3,6,12,9,1.4,145,12,83,53,12,3.4,2,7.5)
>>> minDistance(lst)
2 2
12 12
12 12
>>>

Answer 3

何塞说得有道理。但是，您可以只考虑这些情况，而不关心 return 一个或另一个。

我不认为你需要一个排序算法，但是可能只是一种像这样的 'champion' 算法：

def smallestDistance(self, arr):
    championI = -1
    championJ = -1
    champDistance = sys.maxint
    i = 0
    while i < arr.length:
        j = i + 1
        while j < arr.length:
            if math.fabs(arr[i] - arr[j]) < champDistance:
                championI = i
                championJ = j
                champDistance = math.fabs(arr[i] - arr[j])
            j += 1
        i += 1
    r = [arr[championI], arr[championJ]]
    return r

此函数将 return 一个子数组，其中两个值最接近。请注意，这仅在给定至少两个长数组的情况下才有效。否则，你会抛出一些错误。

我认为称为冒泡排序的流行排序算法可以很好地完成这项工作。虽然运行可能 O(n^2) 时间如果那种事情对你很重要...

这是基于按整数大小对数组进行排序的标准冒泡排序。

 def bubblesort( A ):
  for i in range( len( A ) ):
    for k in range( len( A ) - 1, i, -1 ):
      if ( A[k] < A[k - 1] ):
        swap( A, k, k - 1 )

def swap( A, x, y ):
  tmp = A[x]
  A[x] = A[y]
  A[y] = tmp

如果您坚持使用排序算法来执行此操作，则可以稍微修改算法以适合您的目的。但是，我认为初始函数也能正常工作...

希望对您有所帮助。

使用排序查找列表中最接近的两个数字

Finding the two closest numbers in a list using sorting

sorting

python-2.7

closest-points