algorithm - 位操作 AdHoc 变体

Question

问题:

给定两个已排序数组 A 和 B (大小从 1 到 10^5 不等)，元素在 (1,10 ^5)。您还会得到一个大小为 A 中的最高元素 + B 中的最高元素 的数组 C，所有元素最初都是 0。现在，我们必须像这样更新 C:

for i in A:
    for j in B:
        C[i+j] += 1

并且必须找出最终的 C。

时间限制: 1 秒(因此时间复杂度不应为 n^2)

示例:

A = [2,4]
B = [1,3]
Then C would be = [0,0,1,0,2,0,1] (assuming 1th indexed)

我不确定应该从哪里开始。我试图想办法让我们可以在 C 中一次增加 1 个以上，但找不到。有那么一会儿，我以这种方式思考，假设 A 为二进制字符串:“0101”，我们将它移动 B 中的元素，但同样这也不会导致任何地方。

如有任何帮助，我们将不胜感激。谢谢。

Answer 1

如果您将初始数组视为直方图，则输出为两个输入直方图的卷积。

您可以使用快速傅里叶变换在 O(nlogn) 时间内执行此卷积。

例如，在 Python 中:

import scipy.signal

def hist(X):
    """Prepare a histogram of X"""
    h = [0]*(max(X)+1)
    for x in X:
        h[x] += 1
    return h

A = [2,4]
B = [1,3]
print scipy.signal.fftconvolve(hist(A),hist(B))

对于长度为 10^5 的数组，这在我的计算机上只需要 0.05 秒。