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

Question

如果给我一个整数/浮点数列表，我将如何使用排序找到两个最接近的数字？

Answer 1

这样的方法会做你想要的：

>>> 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 2

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

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

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

Answer 3

何塞有一个有效的观点。但是，您可以只考虑这些情况相同，而不关心返回其中一个。

我不认为你需要一个排序算法，但也许只是一种像这样的“冠军”算法：

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

此函数将返回一个子数组，其中包含最接近的两个值。请注意，这仅适用于至少两个长度的数组。否则，你会抛出一些错误。

我认为流行的排序算法称为冒泡排序会做得很好。虽然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

如果您坚持使用排序算法，您可以稍微修改算法以适应您的目的。但是，我认为初始功能也可以...

希望有帮助。