如果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上成对和的排序列表，或“
开放问题”项目。