python - 算法 : selecting points from a list

Question

我很难找到适合我的问题的算法。
我有两个大的数字列表(或集合)，列表 A 和列表 B。列表 A 已经对实数进行了排序和列表 B 已经排序实数，我想创建一个列表 C，其中包含列表 B 中的选定点，列表 B 中的选择以这种方式工作，从列表 A 中的每个元素(数字)我必须搜索最近的数字(绝对值(A.元素-B.元素)=最小值)。我会举一些例子，因为它很难解释。示例 1:

A= [20.0, 19.6, 19.2]
B= [22.454, 22.224, 21, 20.1, 19.76, 19.72, 19]

C= [20.1, 19.72, 19]

条件:
列表 C 不能有重复点，例如，如果列表 A 中的两个元素共享列表 B 中的相同点(因为它是列表 A 中两个点的最近点)那么列表 A 中的一个点必须从列表 B 中选择第二个最近的点示例 2:

A= [20.0, 19.6, 19.2]
B= [22.454, 22.224, 21, 20.3, 19.9, 19, 18]

C= [20.3, 19.9, 19]
# I it must not choose  C= [19.9, 19, 18] because its not an optimum solution

注意事项:列表 B 总是比列表 A 大至少 4 倍，所以如果 A 有 10 个元素，B 将至少有 40 个元素

所以让我快速地重新解释一下，列表 C 必须对从列表 B 中选择的不重复元素进行排序，从列表 B 中选择的这些点必须最接近列表 A 中的每个元素。

我希望我的解释和我的英语足够好:)请帮我找到一个在 python 2.7 中完成它的好方法谢谢大家

Answer 1

使用二分查找

def binary(arr, val):
    assert len(arr) > 0
    if len(arr) == 1:
        return 0
    l2 = len(arr) // 2
    if abs(arr[l2-1] - val) > abs(arr[l2] - val):
        return l2 + binary(arr[l2:], val)
    else:
        return binary(arr[0:l2], val)

def closest_points(A, B):
    C = []
    for val in A:
        idx = binary(B, val)
        C.append(B[idx])
        B.pop(idx)
    return C

A = [20.0, 19.6, 19.2]
B = [22.454, 22.224, 21, 20.1, 19.76, 19.72, 19]
A.reverse()
B.reverse()
C = closest_points(A, B)
C.reverse()
assert C == [20.1, 19.72, 19]

A = [20.0, 19.6, 19.2]
B = [22.454, 22.224, 21, 20.3, 19.9, 19, 18]
A.reverse()
B.reverse()
C = closest_points(A, B)
C.reverse()
assert C == [20.3, 19.9, 19]

复杂度为len(A)*log(len(B))

---

事实上它确实适用于你的例子，但它不符合你的要求(就像其他基于二分搜索的唯一建议的解决方案:( )在不暴露复杂性的情况下，正确的方法是使用 Iterative closest point 算法。