c++ - 从两个数组中提取紧密对的更快方法？

Question

假设我有两个随机的 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) 时间复杂度，而且似乎效率不高。有没有更好的方法来做到这一点，而不考虑空间成本？

Answer 1

您可以在 O(N log N) 中执行(+ 结果对的数量(可能超过 N log N)):

std::sort(std::begin(A), std::end(A)); // O(N log N)
std::sort(std::begin(B), std::end(B)); // O(N log N)

auto begin = std::begin(B);
auto end = begin;
for (auto v : A) {
    while (begin != std::end(B) && *begin < v - 50) ++begin;
    while (end != std::end(B) && *end < v + 50) ++end;
    for (auto it = begin; it != end; ++it) {
        std::cout << '(' << v << ", " << *it << ")\n";
    }
}

Demo