algorithm - 计算两个数组元素之间的距离

Question

我有 2 个数组 A[] 和 B[] 每个都有 n 个元素，我想计算 A 的每个元素之间的差异> 数组到B数组的元素，输出为差值小于x0(某个值)的元素集合。

例如:A =[1,2,3] B=[2,3,4]
我想要 "1-2","1-3 ","1-4","2-3"...

假设 x0 = 2，所以输出为 ([1,2],[1,3],[2,3]...)。< br/>
我正在使用蛮力方法，获取数组 A 的每个元素并减去 B 的时间复杂度为 O(n^2) 的元素。谁能建议更好的方法？

Answer 1

这个问题的复杂度是output-sensitive ，这意味着，如果所有可能的对都匹配，则 alogirhtm 必须运行 O(n^2) 时间。假设输出小于 O(n*log(n))，则以下 python 代码运行时为 O(n*log(n)):

from bisect import bisect_left, bisect_right
from itertools import repeat

arr1 = [1, 2, 3]
arr2 = sorted([2, 3, 4, 5])

d = 1

result = []
for item in arr1:
    left, right = bisect_left(arr2, item - d), bisect_right(arr2, item + d)
    result += zip(repeat(item), arr2[left:right])

上面的代码对其中一个数组进行排序，然后从已排序的数组中搜索另一项。这需要 O(n*log(n)) 时间对其中一个数组进行排序，然后 O(log(n)) 为每次搜索平分数组。