查找两个已排序数组的前 k 个和

给定两个已排序的数组，大小分别为 n 和 m。你的任务（如果你选择接受它）是输出以下形式的最大 k 和a[i]+b[j].

O(k log k) 解决方案可以在这里找到 http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1132204952;start=。有传言称存在 O(k) 或 O(n) 解决方案。有吗？

我发现您链接上的回复大多含糊且结构不良。这是从 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. The loop is executed k times.
   1. 每次迭代有一个弹出操作。
   2. 每次迭代最多有两次插入操作。
2. 优先级队列的最大大小为O(min(m, n)) O(m + n) O(k)。
3. 优先级队列可以通过给出 log(size) pop 和 insert 的二叉堆来实现。
4. 因此这个算法是 O(k * log(min(m, n))) O(k * log(m + n)) O(k * log(k ））。

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

如果有兴趣的话我可以用 Java 写下来。

编辑：固定复杂性。那里is一种具有我所描述的复杂性的算法，但与此略有不同。您必须小心避免添加某些节点。我的简单解决方案过早地将许多节点添加到队列中。