假设我有两个随机的int
数组,如下:
int A[] = {484, 834, 591, 23, 174, 248, 147, 765};
int B[] = {659, 805, 12, 180, 771, 386, 354, 568, 710, 312, 6, 848};
我希望能够从两个数组中分别找到所有接近的数对,其中两个int
之间的差不大于某个固定值k
,例如50
:
(from A, from B)
(834, 805)
(834, 848)
(591, 568)
(23, 12)
(23, 6)
(174, 180)
(147, 180)
(765, 805)
(765, 771)
一种简单的做法是使用嵌套的 for
循环:
for (int a : A) {
for (int b : B) {
if (abs(a - b) < k)
// find (a, b)
}
}
但这需要 O(n^2)
的时间复杂度,似乎不太高效。是否有更好的方法,无论空间成本如何?