在2个数组中找到第k个最大和的对。

如何解决在2个数组中找到第k个最大和的对。？

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

这个想法很简单。我们将逐一找到第1，第2，..，第k个最大值。但是，即使要考虑配对，(i, j)我们也需要同时选择(i-1, j)和(i,j-1)，因为它们都大于或等于(i, j)。

这很像是将所有n*m对放入堆中，然后删除最大k时间。只有我们不需要所有的n*m配对。

heap.add(pair(0, 0)); // biggest pair// remove max k-1 timesfor (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 elementmax = heap.popMax();maxVal = a[max.i] + b[max.j];

一些事情要考虑。

可以将重复的对添加到堆中，这可以通过哈希来防止。索引需要验证，例如that max.i + 1 < a.length。解决方法

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

[2、3、5、8、13][4、8、12、16]

总和最大的对是

13 + 16 = 2913 + 12 = 258 + 16 = 2413 + 8 = 218 + 12 = 20

因此，总和排名第四的货币对是（13，8）。如何找到具有第k个最大和的对？

我正在寻找涉及最小堆或最大堆的解决方案。