我从一个简单但不太线性的算法开始。我们在array1[0]+array2[0]和之间选择一些值array1[N-1]+array2[N-1]。然后我们确定有多少对和大于该值，有多少对小于。这可以通过使用两个指针迭代数组来完成：当sum太大时，指向第一个数组的指针递增，而sum太小时，指向第二个数组的指针递减。对不同的值重复此过程，并使用二进制搜索（或单面二进制搜索），我们可以找到O（N
log
R）时间中的第K个最大和，其中N是最大数组的大小，R是介于array1[N-1]+array2[N-1]和之间的可能值的数量。array1[0]+array2[0]。仅当数组元素是由小常数限制的整数时，此算法才具有线性时间复杂度。

如果我们在二进制搜索范围内的对和数从O（N 2）减少到O（N
），就立即停止二进制搜索，可能会改进以前的算法。然后，我们用这些对和填充辅助数组（这可以通过稍微修改的两指针算法来完成）。然后，我们使用快速选择算法在此辅助数组中找到第K个最大和。所有这些都不会提高最坏情况的复杂性，因为我们仍然需要O（log
R）二进制搜索步骤。如果我们保留该算法的quickselect部分，但是（为了获得适当的值范围），我们使用比二进制搜索更好的方法怎么办？

我们可以使用以下技巧估算值范围：从每个数组中获取第二个元素，并尝试k/4为这些半数组找到具有秩的对和（递归使用相同的算法）。显然，这应该为所需的值范围提供一些近似值。实际上，此技巧的稍有改进的变体使范围仅包含O（N）个元素。这在以下论文中得到了证明：A.
Mirzaian和E. Arjomandi撰写的“在X +
Y和具有排序的行和列的矩阵中进行选择”。本文包含该算法的详细说明，证明，复杂性分析和除Quickselect以外的算法所有部分的伪代码。如果需要线性最坏情况下的复杂度，则可以使用中位数中位数算法来增强Quickselect
。

该算法的复杂度为O（N）。如果其中一个数组比另一个数组短（M
<N），我们可以假设此较短的数组使用一些非常小的元素扩展到大小N，以便算法中的所有计算都使用最大数组的大小。实际上，我们不需要提取带有这些“添加”元素的对并将其馈送到quickselect，这会使算法更快一点，但不会提高渐近复杂性。

如果k <N，我们可以忽略索引大于k的所有数组元素。在这种情况下，复杂度等于O（k）。如果N <k
N（N-1），我们最好解决相反的问题：第k个最小和。

我将简单的C ++
11实现上传到ideone。代码未优化，也未经过全面测试。我试图使其尽可能接近链接纸中的伪代码。此实现使用std::nth_element，仅允许平均线性复杂度（不允许最坏情况）。

在线性时间中找到第K个和的一种完全不同的方法是基于优先级队列（PQ）。一种变化是在PQ中插入最大的一对，然后重复删除PQ的顶部，而最多插入两对（一个在一个数组中的索引递减，另一对在另一个数组中的索引递减）。并采取一些措施以防止插入重复的对。其他变化是插入所有可能的对，其中包含第一个数组的最大元素，然后重复删除PQ的顶部，而是在第一个数组中插入索引递减且在第二个数组中索引相同的对。在这种情况下，无需担心重复。

OP提到O（K log
K）解决方案，其中PQ被实现为最大堆。但在某些情况下（当数组元素均匀地分布具有有限范围和线性复杂整数只需要平均，而不是最坏情况），我们可以使用O（1）时间优先级队列，例如，如在本文中所描述：“事件驱动的分子动力学模拟的复杂度O（1）优先级队列”，作者Gerald
Paul。这允许O（K）预期时间复杂度。

这种方法的优点是可以按排序的顺序提供前K个元素。缺点是数组元素类型的选择有限，算法更加复杂和缓慢，渐近复杂性更差：O（K）> O（N）。