位操作AdHoc变异

Question

问题：

您将获得两个排序的数组A和B(大小可以从1到10^5不等)，其元素范围为(1,10^5)。您还得到了一个大小为的数组C，即B中A+最高元素中的最高元素，最初所有元素都为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)

我不确定从哪里开始。我试着想一种方法，这样我们一次可以增加超过1英寸的C，但却找不到。有一段时间，我这样想，假设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秒。