我从一个简单但不完全线性时间的算法开始。我们选择一些值array1[0]+array2[0] and array1[N-1]+array2[N-1]。然后我们确定有多少对总和大于该值以及有多少对总和小于该值。这可以通过使用两个指针迭代数组来完成：当总和太大时，指向第一个数组的指针递增；当总和太小时，指向第二个数组的指针递减。对不同的值重复此过程并使用二分搜索（或单边二分搜索），我们可以在 O(N log R) 时间内找到第 K 个最大和，其中 N 是最大数组的大小，R 是之间可能值的数量array1[N-1]+array2[N-1] and array1[0]+array2[0]。仅当数组元素是由小常数限制的整数时，该算法才具有线性时间复杂度。
Previous algorithm may be improved if we stop binary search as soon as number of pair sums in binary search range decreases from O(N2) to O(N). Then we fill auxiliary array with these pair sums (this may be done with slightly modified two-pointers algorithm). And then we use quickselect algorithm to find Kth largest sum in this auxiliary array. All this does not improve worst-case complexity because we still need O(log R) binary search steps. What if we keep the quickselect part of this algorithm but (to get proper value range) we use something better than binary search?
我们可以使用以下技巧来估计值范围：从每个数组中获取每隔一个元素，并尝试找到具有排名的对和k/4对于这些半数组（递归地使用相同的算法）。显然，这应该给出所需值范围的一些近似值。事实上，这个技巧的稍微改进的变体给出了仅包含 O(N) 元素的范围。这在以下论文中得到证明：“X + Y 中的选择以及已排序行和列的矩阵”作者：A. Mirzaian 和 E. Arjomandi http://www.cse.yorku.ca/~andy/pubs/X%2BY.pdf。本文包含算法的详细解释、证明、复杂性分析以及算法所有部分的伪代码（除了快速选择 http://en.wikipedia.org/wiki/Quickselect。如果需要线性最坏情况复杂性，可以通过以下方式增强快速选择中位数的中位数 http://en.wikipedia.org/wiki/Median_of_medians算法。
该算法的复杂度为O(N)。如果其中一个数组比其他数组短 (M
如果 k N(N-1)，我们最好解决相反的问题：第 k 个最小和。
我将简单的 C++11 实现上传到ideone http://ideone.com/qe1YHA。代码未优化且未经过彻底测试。我试图使其尽可能接近链接论文中的伪代码。该实现使用std::nth_element，仅允许平均线性复杂度（不是最坏情况）。
在线性时间内求第 K 个和的完全不同的方法是基于优先级队列 (PQ)。一种变体是将最大的对插入到 PQ，然后重复删除 PQ 的顶部并插入最多两对（一对在一个数组中具有递减索引，另一对在另一个数组中具有递减索引）。并采取一些措施来防止插入重复对。其他变体是插入包含第一个数组的最大元素的所有可能对，然后重复删除 PQ 的顶部，并在第一个数组中插入具有递减索引的对，并在第二个数组中插入相同索引的对。在这种情况下，无需担心重复项。
OP 提到 O(K log K) 解决方案，其中 PQ 被实现为最大堆。但在某些情况下（当数组元素是均匀分布且范围有限的整数，并且仅在平均情况下而不是最坏情况下需要线性复杂度时），我们可以使用 O(1) 时间优先级队列，例如，如本文所述：“事件驱动分子动力学模拟的复杂性 O(1) 优先级队列”作者：Gerald Paul http://arxiv.org/pdf/physics/0606226。这允许 O(K) 预期时间复杂度。
这种方法的优点是可以按排序顺序提供前 K 个元素。缺点是数组元素类型的选择有限，算法更复杂且更慢，渐近复杂度更差：O(K) > O(N)。
