从点列表中获取最近的两个点

Question

我得到了一个 integers/floats 的列表，我需要找到最接近的两个数字。我将如何仅使用嵌套的 for 循环来做到这一点？

Answer 1

对于每个元素，您必须将它与其他每个元素的距离与您之前的 "closest" 值进行比较 - 任何时候此比较产生较小的值，您都会记住该对作为 "two closest" 一个。

所以，很简单：

def find_two_closest(numbers):
    # most distant points:
    delta = max(numbers), min(numbers)
    for i, element in enumerate(numbers):
        for j, sec_element in enumerate(numbers):
            if i == j:
                continue
            if abs(sec_element - element) < abs(delta[0] - delta[1]):
                delta = sec_element, element
    return delta

Answer 2

不需要每两个点检查一次，而且很慢O(n^2)。

我建议：
1) 对输入进行排序。
2) 比较以下每两个值并选择最小的。
假设您使用有效的排序算法，时间会好得多 O(n*log n)。

代码示例：

input = [0, 65, 10, 100, 1231] #whatever you put here; it might be tuple, list, set, range, etc.

def find_closest(input):
    sorted_input = sorted(input)
    best = (sorted_input[-2], sorted_input[-1], sorted_input[-1] - sorted_input[-2])
    for i, val in enumerate(sorted_input[:-1]):
        d = sorted_input[i+1]-val
        if d < best[2]:
            best = (val, sorted_input[i+1], d) 
return best

函数 returns 值和它们之间的距离。

Answer 3

如果这些点是一维的（因为在您的输入中只是像 [1, 4, 6, 2] 这样的数字列表），那么您可以通过对它们进行排序并找到差异最小的：

def smallest_difference(points):
    sorted_points = sorted(points)
    return min(abs(prev - cur) for cur, prev in zip(sorted_points, sorted_points[1:]))

如果要获取最近点而不是最近点之间的距离，请使用min函数的key=参数：

import operator

def smallest_difference(points):
    sorted_points = sorted(points)
    return min(zip(sorted_points, sorted_points[1:]), key=lambda x: abs(x[1] - x[0]))

如果点是二维的（因为在您的输入中是一个包含 2 个元素元组的列表，例如 [(1, 2), (3, 4), (5, 2)]），那么关于此问题的维基百科文章 https://en.wikipedia.org/wiki/Closest_pair_of_points_problem 描述了如何将其扩展到二维.

从点列表中获取最近的两个点

Get the two closest points from a list of points

python

for-loop

closest-points