找到两个阵列的所有可能距离

Question

给定两个排序的数组A和B长度N.每个元素可以包含小于的自然数M.确定所有的组合元素的所有可能的距离A和B.在这种情况下,如果A[i] - B[j] < 0,那么距离是M + (A[i] - B[j]).

示例:

A = {0,2,3}
B = {1,2}
M = 5

Distances = {0,1,2,3,4}

注意:我知道O(N^2)解决方案,但我需要比O(N^2)和更快的解决方案O(N x M).

编辑:数组A,B并Distances包含不同的元素.

Answer 1

您可以通过以下方式获得O(MlogM)复杂性解决方案.

1. 如果i属于A,则准备长度为M的数组Ax,其中Ax [i] = 1(否则为0)
2. 如果我属于B,则准备长度为M的数组Bx,其中Bx [M-1-i] = 1(否则为0)
3. 使用快速傅里叶变换将这两个序列卷积在一起
4. 检查输出数组,非零值对应可能的距离

请注意,FFT通常使用浮点数完成,因此在步骤4中,您可能希望测试输出是否大于0.5,以避免潜在的舍入噪声问题.