这可以在中轻松完成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];

一些事情要考虑。

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