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

Question

给定两个排序的数字数组,我们希望找到具有第k个最大可能总和的对.(一对是第一个数组中的一个元素,第二个数组中是一个元素).例如,使用数组

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

具有最大总和的对是

• 13 + 16 = 29
• 13 + 12 = 25
• 8 + 16 = 24
• 13 + 8 = 21
• 8 + 12 = 20

因此,第四大总和是(13,8).如何找到具有第k个最大可能总和的对？

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

Answer 1

这可以很容易地完成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 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.