performance - 如何找到具有第k个最大和的对？

Question

给定两个排序的数字数组，我们希望找到第k个可能和最大的一对。（一对是第一个数组中的一个元素和第二个数组中的一个元素）。例如，使用数组
[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个最大可能和的一对？
还有，最快的算法是什么？数组已经排序，大小为m和n。
我已经知道o（klogk）解决方案，使用max heap givenhere。
这也是google最喜欢的面试问题之一，他们需要一个o（k）的解决方案。
我也读到有一个O（k）解，我无法理解。
有人能用伪代码解释正确的解决方案吗？
附笔。
请不要将this链接发布为答案/评论。它不包含答案。

Answer 1

我从一个简单但不是很线性的时间算法开始。我们在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（n2）减少到o（n）时，停止二元搜索可以改进原有的算法。然后用这些对和填充辅助阵列（这可以用稍加修改的两指针算法来完成）。然后，利用该算法求出该辅助数组的k个最大和。所有这些都不能改善最坏情况的复杂性，因为我们仍然需要O（log R）二进制搜索步骤。如果我们保留了这个算法的quickselect部分，但是（为了得到合适的值范围），我们使用了比二进制搜索更好的方法呢？
我们可以使用以下技巧估计值范围：从每个数组中获取每一个第二元素，并尝试为这半个数组找到秩k/4的对和（使用相同的递归算法）。显然，这应该给出所需值范围的一些近似值。事实上，这个技巧稍加改进的变体给出了只包含o（n）元素的范围。这在下面的文章中得到了证明："Selection in X + Y and matrices with sorted rows and columns" by A. Mirzaian and E. Arjomandi。本文详细地介绍了除AA>以外的算法的所有部分的算法、证明、复杂度分析和伪代码。如果需要线性最坏情况复杂度，则可以用Quickselect算法进行快速选择。
该算法具有O（n）的复杂性。如果其中一个数组比另一个数组短（m 如果k＜n，我们可以忽略所有索引大于k的数组元素，在这种情况下，复杂性等于O（k）。如果n＜k＜n（n-1），我们的复杂度要比OP中的要求好。如果k> n（n-1），我们最好解相反的问题：k次最小和。
我上传了简单的C++ 11实现到 Median of medians。代码没有经过优化，也没有经过彻底测试。我试图使它尽可能接近伪代码的链接文件。这个实现使用了cc，它只允许线性复杂度（不是最坏情况）。
一种完全不同的求线性时间第k和的方法是基于优先级队列（pq）。一种变化是向pq插入最大的对，然后重复删除pq的顶部，而不是最多插入两对（一个数组中的索引递减，另一个数组中的索引递减）。并采取措施防止插入重复对。另一个变化是插入包含第一个数组最大元素的所有可能对，然后重复删除pq的顶部，而不是在第一个数组中插入索引递减的对，在第二个数组中插入索引相同的对。在这种情况下，不必为复制品操心。
op提到了o（k logk）解决方案，其中pq被实现为最大堆。但在某些情况下（当数组元素在有限的范围内均匀分布整数时，只需要平均值，而不是最坏情况），我们可以使用O（1）时间优先队列，如本文所述： ideone。这允许O（k）期望的时间复杂度。
这种方法的优点是可以按排序顺序提供前k个元素。缺点是数组元素类型的选择有限，算法更复杂和较慢，较差的渐近复杂度：O（k）＞O（n）。