找到两个有序阵列的前k个总和 [英] Find the top k sums of two sorted arrays

问题描述

您给出的尺寸n和m的两个排序阵列，分别。你的任务（如果您选择接受它），是输出形式的最大ķ金额 A [I] + B [J] 。

A○（K数K）解决方案<一href="http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1132204952;start=">can在这里找到。有一个O（K）或O（n）的解决方案的传言。做一件存在吗？

解决方案

我发现在你的链接的答复大多是模糊的，结构化的很差。这里有一个<打击> 0开始（K *日志（分钟（M，N））） O（K *日志（M + N））的算法。

假设它们进行排序下降。想象一下，你计算的数额的M * n矩阵如下：

 为我从0到m
    对于j从0到n
        款项[I] [J] = A [1] + B [J]。
 

在此矩阵中，值单调减少向下和向右。考虑到这一点，这里是一个算法，从而减小款项通过执行该矩阵的图形搜索。

 问：优先级队列（递减）：=空优先级队列
添加（0,0）到q优先一个[0] + B [0]
而K＆GT; 0：
    K--
    X：=弹出q
    输出x
    （I，J）：整型元组，INT：= x的位置
    如果我＆LT; M：
        添加第（i + 1，j）的到q与优先级的[I + 1] + B [j]的
    如果J＆LT; N：
        添加（I，J + 1）到q与优先级的[I] + B [J + 1]
 

分析：

1. 在该循环执行k次。
   1. 有每个迭代1弹出操作。
   2. 有多达每次迭代两个插入操作。
2. 的优先级队列的最大大小是<打击> O（分钟（M，N）） O（M + N）。
3. 的优先级队列可以用二元堆奉献日志（尺寸）弹出来实现，并插入。
4. 因此，该算法是<打击> O（K *日志（分钟（M，N））） O（K *日志（M + N））。

请注意，一般的优先级队列的抽象数据类型需要被修改以忽略重复条目。或者，你可以认为加入到队列前，要求加入该组首先检查，并从队列中弹出后，将删除该组一组独立的结构。无论这些想法会恶化时间和空间复杂度。

我可以写这件事在Java中，如果有任何兴趣。

编辑：固定的复杂性。那里的是的一种算法，具有I中描述的复杂性，但它是从这个略有不同。你将不得不小心避免增加某些节点。我简单的解决方案增加了很多节点队列prematurely。

You are given two sorted arrays, of sizes n and m respectively. Your task (should you choose to accept it), is to output the largest k sums of the form a[i]+b[j].

A O(k log k) solution can be found here. There are rumors of a O(k) or O(n) solution. Does one exist?

解决方案

I found the responses at your link mostly vague and poorly structured. Here's a start with a O(k * log(min(m, n))) O(k * log(m + n)) algorithm.

Suppose they are sorted decreasing. Imagine you computed the m*n matrix of the sums as follows:

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

In this matrix, values monotonically decrease down and to the right. With that in mind, here is an algorithm which performs a graph search through this matrix in order of decreasing sums.

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]

Analysis:

1. The loop is executed k times.
   1. There is one pop operation per iteration.
   2. There are up to two insert operations per iteration.

2. The maximum size of the priority queue is O(min(m, n)) O(m + n).
3. The priority queue can be implemented with a binary heap giving log(size) pop and insert.
4. Therefore this algorithm is O(k * log(min(m, n))) O(k * log(m + n)).

Note that the general priority queue abstract data type needs to be modified to ignore duplicate entries. Alternately, you could maintain a separate set structure that first checks for membership in the set before adding to the queue, and removes from the set after popping from the queue. Neither of these ideas would worsen the time or space complexity.

I could write this up in Java if there's any interest.

Edit: fixed complexity. There is an algorithm which has the complexity I described, but it is slightly different from this one. You would have to take care to avoid adding certain nodes. My simple solution adds many nodes to the queue prematurely.

这篇关于找到两个有序阵列的前k个总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！