找到对在2个阵列，第k个最大的一笔 [英] Find the pair across 2 arrays with kth largest sum

问题描述

由于两个数字排序的数组，我们要找到对的第k最大可能的总和。 （一对是来自第一阵列的一个元素和从所述第二阵列的一个元素）。例如，数组

Given two sorted arrays of numbers, we want to find the pair with the kth largest possible sum. (A pair is one element from the first array and one element from the second array). For example, with arrays

• [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最大可能的总和？

So the pair with the 4th largest sum is (13, 8). How to find the pair with the kth largest possible sum?

我要寻找涉及任何一个最小堆还是最大堆的解决方案。

I am looking for a solution involving either a min heap or a max heap.

推荐答案

这可以很容易地在完成O（K *稳定常数）。我只能假设数组按降序排序，以简化符号。

That can be easily done in O(k*logk). I'll only assume arrays are sorted in descending order, to simplify notation.

我们的想法很简单。我们会找到第一，第二，...，第k个最大值一个接一个。但是，即使考虑对（I，J）我们需要有两个（I-1，J）和（I，J-1）已被选中，是因为他们都是比（I，J）。

The idea is simple. We'll find 1st, 2nd, .., k-th maximum values one by one. But to even consider pair (i, j) we need to have both (i-1, j) and (i, j-1) already selected, because they both are greater or equal than (i, j).

这是，如果我们全部推 N * M 双进堆很像然后取出最高 K 次。只有我们并不需要所有 N * M 对。

It's much like if we push all n*m pairs into the heap and then remove max k times. Only we don't need all n*m pairs.

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];

有些事情要考虑。

Some things to consider.

• 重复的对可以添加到堆，这可以是与pvented散列$ P $
• 索引需要验证，如该 max.i + 1＆LT;则为a.length 。

这篇关于找到对在2个阵列，第k个最大的一笔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！