位操作 AdHoc 变体

Question

问题：

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

位操作 AdHoc 变体

Bit Manipulation AdHoc Variation

algorithm

bit-manipulation

time-complexity

adhoc