algorithm - 找出两个排序数组的前 k 个和

Question

给定两个有序数组，大小分别为 n 和 m。您的任务(如果您选择接受)是输出 a[i]+b[j] 形式的最大 k 个和。

O(k log k) 解 can be found here .有传言说 O(k) 或 O(n) 解决方案。有吗？

Answer 1

我发现您的链接中的回复大多含糊不清且结构不佳。这是一个 O(k * log(min(m, n))) O(k * log(m + n)) O(k * log( k)) 算法。

假设它们按降序排列。假设您按如下方式计算了总和的 m*n 矩阵:

for i from 0 to m
    for j from 0 to n
        sums[i][j] = a[i] + b[j]

在此矩阵中，值单调向下和向右递减。考虑到这一点，这里有一个算法，该算法按总和递减的顺序通过该矩阵执行图形搜索。

q : priority queue (decreasing) := empty priority queue
add (0, 0) to q with priority a[0] + b[0]
while k > 0:
    k--
    x := pop q
    output x
    (i, j) : tuple of int,int := position of x
    if i < m:
        add (i + 1, j) to q with priority a[i + 1] + b[j]
    if j < n:
        add (i, j + 1) to q with priority a[i] + b[j + 1]

分析:

1. 循环执行了k次。
   1. 每次迭代有一个弹出操作。
   2. 每次迭代最多有两个插入操作。
2. 优先级队列的最大大小是 O(min(m, n)) O(m + n) O(k)。
3. 优先级队列可以用二进制堆实现，提供 log(size) 弹出和插入。
4. 因此这个算法是 O(k * log(min(m, n))) O(k * log(m + n)) O(k *日志(k))。

请注意，需要修改通用优先级队列抽象数据类型以忽略重复条目。或者，您可以维护一个单独的集合结构，该结构在添加到队列之前首先检查集合中的成员资格，并在从队列中弹出后从集合中删除。这些想法都不会恶化时间或空间的复杂性。

如果有任何兴趣，我可以用 Java 编写。

编辑:修复了复杂性。 有一种算法具有我描述的复杂性，但它与这个略有不同。您必须小心避免添加某些节点。我的简单解决方案过早地将许多节点添加到队列中。