在两个排序数组的有序叉和中查找前 k 个元素的最快算法

Question

我有两个已排序的浮点数数组

x[]

和

y[]

。数组大小分别为

n

和

m

。

我需要找到有序的第

k

，

k

<<

min(m, n)

，交叉和数组中的元素，即

s = {x[0] + y[0], x[0] + y[1], ..., x[0] + y[m-1], x[1] + y[0], x[1] + y[1], ..., x[1] + y[m-1], ..., x[n-1] + y[0], x[n-1] + y[1], ..., x[n-1] + y[m-1]}

。

我当前的方法或多或少是连接数组

{x[0] + y[0], x[0] + y[1], ..., x[0] + y[m-1]}

,

{x[1] + y[0], x[1] + y[1], ..., x[1] + y[m-1]}

,

...

{x[k-1] + y[0], x[k-1] + y[1], ..., x[k-1] + y[m-1]}

,

{y[0] + x[0], y[0] + x[1], ..., y[0] + x[n-1]}

,

{y[1] + x[0], y[1] + x[1], ..., y[1] + x[n-1]}

,

...

{y[k-1] + x[0], y[k-1] + x[1], ..., y[k-1] + x[n-1]}

,

然后选择第

k

个元素。

我的猜测是这个问题在卷积相关算法中应该具有一定的意义。最快的实现方法是什么？

Answer 1

这是 @Jetunsaure 提出的算法的 python 实现。它执行计算最终结果所需的最小加法量。

def kth_smallest_sum(x, y, k):
    indexes = [0] * k
    sums = [[None] * k for _ in range(k)]
    row = 0
    for _ in range(k):
        msum = None
        for r in range(row+2):      # this is safe as k < min(len(x), len(y))
            c = indexes[r]
            if sums[r][c] is None:
                sums[r][c] = x[r] + y[c]
            if msum is None or sums[r][c] < msum:
                minr, msum = r, sums[r][c]
        ksum = msum
        indexes[minr] += 1
        row = max(row, minr)
    return ksum

使用示例：

kth_smallest_sum([i * 7 for i in range(10)], [i * 5 for i in range(10)], 8)

输出：

17