C++ 程序查找两个数组中和最小的 k 对

给定两个升序整数数组 arr1[] 和 arr2[] 以及一个整数 k。确定 k 对和最小的数对，其中一个元素属于 arr1[]，另一个元素属于 arr2[]。

示例

方法一（简单）

找出所有数对并记录它们的和。此步骤的时间复杂度为 O(n1 * n2)，其中 n1 和 n2 是输入数组的大小。

然后按和对数对进行排序。此步骤的时间复杂度为 O(n1 * n2 * log (n1 * n2))。

• 总时间复杂度为 O(n1 * n2 * log (n1 * n2))。
• 辅助空间为 O(n1*n2)。

方法二（高效）

从最小和的数对开始，我们一个接一个地找到 k 个最小和的数对。目标是跟踪对于每个元素 array1[i1] 已经检查过的所有 array2[] 元素，以便在一次迭代中我们只考虑下一个元素。为此，我们使用一个索引数组 indexno2[] 来维护另一个数组中下一个元素的索引。它简单地指示在每次迭代中第二个数组的哪个元素应该添加到第一个数组的元素中。对于构成下一个最小值对的元素，我们增加索引数组中的值。

C++ 中的实现

输出

(1, 2) (1, 4) (3, 2) (3, 4)

• 时间复杂度将为 O(k*n1)。
• 辅助空间将为 O(n1)。

方法三：排序、最小堆和 Map

我们不应该蛮力地遍历所有可用的和组合，而应该开发一种策略来将搜索空间缩小到可能的候选和组合。

1. 在 C++ 中，创建一个最小堆，即 priority_queue，用于存储和组合以及构成和的数组 A 和 B 中组件的索引。堆按和排序。
2. 使用两个数组中的条目索引和最小可能的和组合，即 (A[0] + B[0]) (0, 0) 来初始化堆。在最小堆中，元组将是 (A[0] + B[0], 0, 0)。堆按第一个值排序，即两个项目的和。
3. 弹出堆以获取当前最小和以及构成和的元素索引。假设元组为 (sum, i, j)。
   • 将 (A[i + 1] + B[j], i + 1, j) 和 (A[i] + B[j + 1], i, j + 1) 插入最小堆中，但要确保索引对 (i + 1, j) 和 (i, j + 1) 尚未存在。在 C++ 中，我们可以使用 set 来测试这一点。
   • 重复步骤 4 直到 K 次。

C++ 中的实现

输出

(1, 2)
(1, 4)
(1, 5)
(1, 9)

• 由于我们正在使用额外空间，因此辅助空间将为 O(n)。
• 假设 k<=n，则时间复杂度将为 O(n*logn)。