algorithm - 如何在 setA + setB 这样的成对和中找到第 k 个最大的数？

Question

这里有两个整数集，比如A和B我们可以得到另一个集合C，其中每个元素都是A中的元素a和B中的元素b之和。

例如，A = {1,2}，B = {3,4}，我们得到 C = {4, 5, 6} 其中 4=1+3， 5=1+4=2+3， 6=2+4

现在我想找出集合 C 中第 k 个最大的数字是哪个，例如在上面的例子中 5 是第 2 个最大的数字。

有没有高效的解决方案？

我知道成对求和排序是一个悬而未决的问题，并且有一个 n^2 的下限。但由于只需要第 k 个最大的数，也许我们可以借鉴 O(n) 算法在未排序的数组中查找中位数。

谢谢。

Answer 1

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

特别是，我正在考虑以下空间的最佳优先搜索:(a,b) 表示第一个列表 A 中的第 ath 个项目添加到第二个 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在这种情况下，做同样的事情，但使用相反的优先级队列顺序和探索顺序(或者，只是取反和反转值，得到第 (N-k) 个最少，然后取反并返回答案)。

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