如何在成对的和中找到第k个最大数字，如setA + setB？

如何在成对的和中找到第k个最大数字，如setA + setB？

如果k非常接近1或N，则可以简单地运行任何延迟生成排序总和的算法，直到d出第k个或第k个项目。

特别是，我正在考虑以下空间的最佳优先搜索：（a，b）表示第一个列表A中的第a个项目，第二个列表B中的第b个项目添加到第b个项目中。

保留成本=（a，b）= A [a] + B [b]的最佳=最低优先级队列对（a，b）。

从优先级队列中的（1,1）开始，这是最小值。

Repeat until k items popped:  pop the top (a,b) if a<|A|, push (a+1,b) if a=1 and b<|B|, push (a,b+1)

这为您提供了锯齿状梳状连接，并使您不必标记阵列中访问的每个（a，b）。注意cost（a + 1，b）> = cost（a，b）和cost（a，b + 1）>
= cost（a，b）是因为对A和B进行了排序。

这是一张梳子的图片，用于显示上面的后继生成规则（从左上角开始； a是水平方向）：

|-------|-------|-------

这是对（最多）所有| A | * | B |的最佳优先探索 元组及其和。

请注意，在d出k之前推送的最可能项是2 * k，因为每个项都有1个或2个后继项。这是一种可能的队列状态，其中推送到队列中的项目被标记为

*

：

|--*----|-*-----*-------

*

边界上方和左侧的所有内容均已d出。

对于这种

N-k<k

情况，请执行相同的 *** 作，但优先级队列顺序和探索顺序相反（或者，只需取反并取反值，得到第（Nk）个最低值，然后取反并返回答案）。

另请参阅：SO上成对和的排序列表，或“
开放问题”项目。