如果k非常接近1或N，则可以简单地运行任何延迟生成排序总和的算法，直到弹出第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 |的最佳优先探索 元组及其和。
请注意，在弹出k之前推送的最可能项是2 * k，因为每个项都有1个或2个后继项。这是一种可能的队列状态，其中推送到队列中的项目被标记为
*：
|--*----|-*-----*-------
*边界上方和左侧的所有内容均已弹出。
对于这种
N-k<k情况，请执行相同的操作，但优先级队列顺序和探索顺序相反（或者，只需取反并取反值，得到第（Nk）个最低值，然后取反并返回答案）。
另请参阅：SO上成对和的排序列表，或“
开放问题”项目。
