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

Question

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

Answer 1

不需要检查每两个点，而且速度很慢 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

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

Answer 2

[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:]))

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

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)]），那么针对此问题的 Wikipedia 文章https://en.wikipedia.org/wiki/Closest_pair_of_points_problem描述了如何将其扩展到二维。

Answer 3

对于每个元素，您必须将它与其他每个元素的距离与您之前的“最接近”值进行比较——只要这种比较产生较小的值，您就会记住该对是“两个最接近”的值。

所以，这很简单：

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