问如何在像setA + setB这样的两两和中找到第k个最大数？

EN

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

特别地，我在考虑以下空间的最佳优先搜索：(a，b)意味着来自A的ath项，第一个列表，从B添加到bth，第二个列表。

保持在成本(a，b) = Aa+Bb的best=lowest优先级队列对(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的情况，做同样的事情，但是使用颠倒的优先级队列顺序和探索顺序(或者，只需否定和反转这些值，获得最小的第(N-k)个，然后否定并返回答案)。

另请参阅:成对求和on SO的排序列表，或Open problems project。

排序数组A&B: O(mlogm + nlogn)应用一种改进的算法来合并两个排序的数组: O(m+n)，即在每个点上，u求这两个元素的和。当C中有第(m+n-k+1)个元素时，停止合并。该元素本质上是第k个最大的元素。例：{1,2} & {3,4}：排序C：{1+3，(1+4)|(2+3),2+4}

那么，O(n)将是一个下界(可能不是很严格)，否则您可以运行O(n)算法n次以获得O(n^2)中的排序列表。

你能假设这两个集合是排序的吗(你是按照上面的排序顺序来表示它们的)？如果是这样的话，你可以通过“提前退出”，从最后一对元素开始，等等，得到一些平均情况下更好的东西。