在两个数组中找到第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大可能总和的和对？

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

- TimeToCodeTheRoad

---

这个问题不明确、含糊、不完整，现在已经不再是这样了。投票重新开放。 - Colonel Panic

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。

- Nikita Rybak

---

@Nikita：感谢你的努力！我在想，为什么你不考虑i+1和第二个数组中最大的元素？我的意思是，为什么要max.i+1，max.j，而不是max.i+1和第二个数组中的第一个元素。 - TimeToCodeTheRoad

当我们处理(i,0)时，@TimeToCodeTheRoad (i+1,0)已经被添加到堆中。而我们已经处理了(i,0)，因为a[i]+b[0] >= a[i] + b[j]（好吧，如果它们相等，我们可能没有处理，但你可以看到这在正确性方面没有任何影响）。 - Nikita Rybak

@Nikita：再次感谢！另外，为什么我们不考虑数组A的第一个元素和第二个数组的j+1个元素呢？我非常感激你的帮助。请帮帮我。 - TimeToCodeTheRoad

@Nikita：我想给你更多的积分，而不仅仅是选择你的答案。有什么办法吗？ :) - TimeToCodeTheRoad

@TimeToCodeTheRoad 我只是开玩笑，如果吓到你了很抱歉 :) - Nikita Rybak

Answer 2

这是我的答案，我认为它运行良好，但有人能告诉我它的复杂度吗？

谢谢

int ksum( int a[], int n, int b[], int m, int maxk )
{

    std::vector<int> results;
    int* check = new int[m*n];
    memset( check, 0, n*m*sizeof(int) );

    int finali, finalj;
    int starti = 0, startj = 0;
    for( int k=1; k<maxk+1; ++k )
    {
        int max = 0;
        int maxi=n, maxj=m;
        for( int i=starti; i<n && i<k; ++i )
        {
            if( i>maxj )
                break;
            for( int j=i; j<m && j<k; ++j )
            {
                if( i>maxi && j>=maxj )
                    break;
                if( check[i*m+j] == 0 )
                {
                    int tmp = a[i]+b[j];
                    if( tmp>max )
                    {
                        max = tmp;
                        finali = i, finalj = j;
                    }
                    maxi = i, maxj = j;
                    break;
                }
            }
        }
        starti = finali;

        maxi=n, maxj=m;
        for( int j=startj; j<n && j<k; ++j )
        {
            if( j>maxi )
                break;
            for( int i=j; i<m && i<k; ++i )
            {
                if( j>maxj && i>=maxi )
                    break;
                if( check[i*m+j] == 0 )
                {
                    int tmp = a[i]+b[j];
                    if( tmp>max )
                    {
                        max = tmp;
                        finali = i, finalj = j;
                    }
                    maxi = i, maxj = j;
                    break;
                }
            }
        }
        startj = finalj;

        if( max > 0 )
        {
            check[finali*m+finalj] = 1;
            results.push_back( max );
        }
    }

    delete[] check;
    if( maxk > results.size() )
        return 0;
    else
        return results[maxk-1];
}

int _tmain(int argc, _TCHAR* argv[])
{
    int a[] = {10,8,6,4,1};
    int b[] = {9,6,3,2,1};
    int res = ksum( a, 5, b, 5, 9 );
    return 0;
}

- Vince

Answer 3

我明白您想要一个堆，但这并不是最有效的解决方案，正如 phimuemue 指出的那样。

您可以对两个数组进行 max_heap，然后在根处分别设置一个迭代器。此时，您将拥有最大的总和。

现在，在每一步中，找到两个指针的子节点和邻居中尚未访问的最大节点--这是下一个最大的总和。将相应堆中的指针移动到该位置。

重复 k 次。

- Vanwaril

---

这个语句“在每一步中，将指针指向两个值中较小的一个，并将其遍历到其子节点和邻居的最大值”真的可靠吗？以此为例，heap1 [7, 1, 2]，heap2 [8, 6, 7]。毫无疑问，最大的总和是7（来自heap1）+ 8（来自heap2）。但第二大的总和是7（来自heap1）+ 7（来自heap2），而不是2（来自heap1）+ 8（来自heap2）。谢谢！ - Summer_More_More_Tea

啊，你说得对。我编辑了我的回答。 - Vanwaril

很难理解你在做什么!! 是否可以展示一些伪代码以获得更好的清晰度。 - faizan