algorithm - 在 2 个数组中找到具有第 k 个最大总和的对

Question

给定两个排序的数字数组，我们想要找到具有第 k 个最大可能和的对。一对是第一个数组中的一个元素和第二个数组中的一个元素。例如，使用数组

• [2, 3, 5, 8, 13]
• [4, 8, 12, 16]

总和最大的对是:

1. 13 + 16 = 29
2. 13 + 12 = 25
3. 8 + 16 = 24
4. 13 + 8 = 21
5. 8 + 12 = 20

因此和数第 4 大的对是 (13, 8)。如何找到和数第 k 大的对？

我预计解决方案可能涉及最小堆或最大堆。

Answer 1

这可以在 O(k*logk) 中轻松完成.我只假设数组按降序排序，以简化符号。

这个想法很简单。我们将一一找到第 1、第 2、..、第 k 个最大值。但甚至考虑对 (i, j)我们需要同时拥有 (i-1, j)和 (i, j-1)已经选择，因为它们都大于或等于 (i, j) .

这很像我们推送所有 n*m pairs 放入堆中，然后删除 max k次。只是我们不需要所有 n*m对。

heap.add(pair(0, 0));  // biggest pair

// remove max k-1 times
for (int i = 0; i < k - 1; ++i) {
    // get max and remove it from the heap
    max = heap.popMax();

    // add next candidates
    heap.add(pair(max.i + 1, max.j));
    heap.add(pair(max.i, max.j + 1));
}

// get k-th maximum element
max = heap.popMax();
maxVal = a[max.i] + b[max.j];

一些需要考虑的事情。

• 可以将重复的对添加到堆中，这可以通过散列来防止。
• 需要验证索引，例如那max.i + 1 < a.length .