找到两个排序数组的前k个和

Question

您将获得两个排序的数组,分别为n和m.你的任务(你应该选择接受它)是输出表格的最大k和a[i]+b[j].

可在此处找到 AO(k log k)解决方案.有传言称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. 每次迭代都有一个pop操作.
   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编写这个.

编辑:修复复杂性.还有就是它有我所描述的复杂的算法,但它是从这个略有不同.您必须小心避免添加某些节点.我的简单解决方案过早地向队列中添加了许多节点.