时间戳

首页 > 解决方案 > 从两个数组中提取紧密对的更快方法？

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

问题描述

假设我有两个随机数组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};

我希望分别从两个数组中找到所有接近的对，其中两个 s 之间的差异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)时间复杂度，而且似乎效率不高。有没有更好的方法来做到这一点，而不考虑空间成本？

标签： c++algorithmsorting

解决方案

您可以在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";
    }
}

演示

推荐阅读