给定两个排序的数字数组，我们希望找到具有第 k 个最大可能和的对。（一对是第一个数组中的一个元素和第二个数组中的一个元素）。例如，使用数组
总和最大的对是
所以总和第 4 大的对是 (13, 8)。如何找到具有第 k 个最大可能和的对？
另外，最快的算法是什么？数组已经排序，大小为 M 和 N。
我已经知道使用此处给出的 Max-Heap的O(Klogk)解决方案。
这也是谷歌最受欢迎的面试问题之一，他们需要一个O(k) 的解决方案。
我还在某处读到存在一个O(k)解决方案，但我无法弄清楚。
有人可以用伪代码解释正确的解决方案吗？
PS请不要将此链接发布为答案/评论。它不包含答案。
我从一个简单但不是很线性的时间算法开始。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) 二进制搜索步骤。如果我们保留这个算法的快速选择部分，但是（为了获得适当的值范围）我们使用比二分搜索更好的东西怎么办？
k/4我们可以使用以下技巧估计值范围：从每个数组中获取每个第二个元素，并尝试为这些半数组找到具有秩的对和（递归使用相同的算法）。显然，这应该为所需的值范围提供一些近似值。事实上，这个技巧的稍微改进的变体给出了只包含 O(N) 元素的范围。这在以下论文中得到证明：A. Mirzaian 和 E. Arjomandi 的“X + Y 中的选择和具有排序的行和列的矩阵”。本文包含算法的详细解释、证明、复杂性分析以及除Quickselect之外的所有算法部分的伪代码。如果需要线性最坏情况复杂度，可以使用中位数算法的中值来增强快速选择。
该算法的复杂度为 O(N)。如果其中一个数组比另一个数组短（M < N），我们可以假设这个较短的数组用一些非常小的元素扩展到大小 N，以便算法中的所有计算都使用最大数组的大小。我们实际上不需要提取带有这些“添加”元素的对并将它们提供给快速选择，这使算法更快一点，但不会提高渐近复杂度。
如果 k < N 我们可以忽略所有索引大于 k 的数组元素。在这种情况下，复杂度等于 O(k)。如果 N < k < N(N-1) 我们只是比 OP 中要求的复杂性更好。如果 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)。
如果最后两个解在 (a1, b1), (a2, b2)，那么在我看来只有四个候选解 (a1-1, b1) (a1, b1-1) (a2-1, b2 ) (a2, b2-1)。这种直觉可能是错误的。当然，每个坐标最多有四个候选，其次高的是 16 对中的（a in {a1,a2,a1-1,a2-1}，b in {b1,b2,b1-1,b2- 1}）。没关系）。
（不，不是，仍然不确定这是否可能。）
另一个问题中的最大堆算法简单、快速且正确。不要敲它。这也很好解释。https://stackoverflow.com/a/5212618/284795
可能没有任何 O(k) 算法。没关系，O(k log k) 几乎一样快。
编辑：这不起作用。我留下了答案，因为显然我不是唯一一个有这种想法的人；见下面的讨论。一个反例是 x = (2, 3, 6), y = (1, 4, 5) 和 k=3，其中算法给出 7 (3+4) 而不是 8 (3+5)。
设x和y为两个数组，按降序排列；我们要构造第K-th 个最大的和。
变量是：i第一个数组（元素x[i]）中j的索引，第二个数组（元素y[j]）中的索引，以及k总和的“顺序”（kin 1..K），从某种意义上说，这S(k)=x[i]+y[j]将是k满足您条件的第一个更大的总和（这是循环不变量）。
从(i, j)等于开始(0, 0)：显然，S(1) = x[0]+y[0]。
k从1到，做K-1：
x[i+1]+ y[j] > x[i] + y[j+1]，那么i := i+1（并且j不会改变）；别的j:=j+1要查看它是否有效，请考虑您有S(k) = x[i] + y[j]. 然后，S(k+1)是小于（或等于） 的最大和S(k)，例如至少一个元素（i或j）发生变化。不难看出其中一个i或j应该改变。如果发生变化，您可以通过设置i来构造小于的更大总和，因为它是递减的，并且所有的都大于。这同样适用于，表明要么要么。S(k)i=i+1xx[i'] + y[j]i' < iS(k)jS(k+1)x[i+1] + y[j]x[i] + y[j+1]
因此，在循环结束时，您找到了K第 -th 个更大的总和。
tl; dr：如果您在每次迭代中向前看并向后看，您可以从结尾（最高）开始并O(K)及时回溯。
尽管我相信这种方法背后的洞察力是合理的，但下面的代码目前还不是很正确（见评论）。
让我们看看：首先，对数组进行排序。因此，如果数组是a和b长度为M和N，并且按照您对它们的排列，最大的项目分别位于插槽M和N中，最大的对总是a[M]+b[N]。
现在，第二大对是什么？它可能会有一个{a[M],b[N]}（它不能同时有两个，因为这又是最大的一对），并且至少有一个{a[M-1],b[N-1]}. 但是，我们也知道，如果我们选择a[M-1]+b[N-1]，我们可以通过从同一个列表中选择较大的数字来使其中一个操作数更大，因此它的最后一列中只有一个数字，倒数第二列中只有一个数字。
考虑以下两个数组：a = [1, 2, 53]; b = [66, 67, 68]. 我们的最高对是53+68。如果我们输掉这两个中较小的那个，我们的对是68+2; 如果我们失去更大的，它是53+67。所以，我们必须向前看，以决定我们的下一对将是什么。最简单的前瞻策略是简单地计算两个可能对的总和。这总是需要两次加法，每次转换需要两次比较（三个因为我们需要处理总和相等的情况）；让我们称之为成本Q）。
起初，我很想重复 K-1 次。但是有一个障碍：下一个最大的一对实际上可能是我们可以有效地制作的另一对{{a[M],b[N]}, {a[M-1],b[N-1]}。所以，我们也需要往后看。
所以，让我们编写代码（python，应该是 2/3 兼容的）：
def kth(a,b,k):
M = len(a)
N = len(b)
if k > M*N:
raise ValueError("There are only %s possible pairs; you asked for the %sth largest, which is impossible" % M*N,k)
(ia,ib) = M-1,N-1 #0 based arrays
# we need this for lookback
nottakenindices = (0,0) # could be any value
nottakensum = float('-inf')
for i in range(k-1):
optionone = a[ia]+b[ib-1]
optiontwo = a[ia-1]+b[ib]
biggest = max((optionone,optiontwo))
#first deal with look behind
if nottakensum > biggest:
if optionone == biggest:
newnottakenindices = (ia,ib-1)
else: newnottakenindices = (ia-1,ib)
ia,ib = nottakenindices
nottakensum = biggest
nottakenindices = newnottakenindices
#deal with case where indices hit 0
elif ia <= 0 and ib <= 0:
ia = ib = 0
elif ia <= 0:
ib-=1
ia = 0
nottakensum = float('-inf')
elif ib <= 0:
ia-=1
ib = 0
nottakensum = float('-inf')
#lookahead cases
elif optionone > optiontwo:
#then choose the first option as our next pair
nottakensum,nottakenindices = optiontwo,(ia-1,ib)
ib-=1
elif optionone < optiontwo: # choose the second
nottakensum,nottakenindices = optionone,(ia,ib-1)
ia-=1
#next two cases apply if options are equal
elif a[ia] > b[ib]:# drop the smallest
nottakensum,nottakenindices = optiontwo,(ia-1,ib)
ib-=1
else: # might be equal or not - we can choose arbitrarily if equal
nottakensum,nottakenindices = optionone,(ia,ib-1)
ia-=1
#+2 - one for zero-based, one for skipping the 1st largest
data = (i+2,a[ia],b[ib],a[ia]+b[ib],ia,ib)
narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data
print (narrative) #this will work in both versions of python
if ia <= 0 and ib <= 0:
raise ValueError("Both arrays exhausted before Kth (%sth) pair reached"%data[0])
return data, narrative
对于那些没有 python 的人，这里有一个 ideone：http: //ideone.com/tfm2MA
在最坏的情况下，我们在每次迭代中进行 5 次比较，以及 K-1 次迭代，这意味着这是一个 O(K) 算法。
现在，可能可以利用有关值之间差异的信息来稍微优化这一点，但这实现了目标。
这是一个参考实现（不是O(K)，但将始终有效，除非存在极端情况，即对具有相等的总和）：
import itertools
def refkth(a,b,k):
(rightia,righta),(rightib,rightb) = sorted(itertools.product(enumerate(a),enumerate(b)), key=lamba((ia,ea),(ib,eb):ea+eb)[k-1]
data = k,righta,rightb,righta+rightb,rightia,rightib
narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data
print (narrative) #this will work in both versions of python
return data, narrative
这将计算两个数组（即所有可能的对）的笛卡尔积，按总和对它们进行排序，并取第 k 个元素。该enumerate函数用其索引装饰每个项目。
[2, 3, 5, 8, 13]
[4, 8, 12, 16]
Merge the 2 arrays and note down the indexes in the sorted array. Here is the index array looks like (starting from 1 not 0)
[1, 2, 4, 6, 8] [3, 5, 7, 9]
Now start from end and make tuples. sum the elements in the tuple and pick the kth largest sum.