如何在成对总和中找到第k个最大数,如setA + setB？

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较低的时间界限.但由于只需要第k个最大数,因此我们可以从O(n)算法中学习未排序数组中的中位数.

谢谢.

Answer 1

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

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

保留在最佳 = 最低优先级队列对 (a,b) 中，成本 (a,b) = A[a]+B[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）个最小值，然后取反并返回答案）。