共同显著差异数

Question

给定两个数组A和B。任务查找公共不同的数目(两个数组中元素的差异)。例子：

A=[3,6,8]
B=[1,6,10]

so we get differenceSet for A
differenceSetA=[abs(3-6),abs(6-8),abs(8-3)]=[3,5,2]
similiarly
differenceSetB=[abs(1-6),abs(1-10),abs(6-10)]=[5,9,4]

Number of common elements=Intersection :{differenceSetA,differenceSetB}={5}
Answer= 1

我的方法O(N^2)

int commonDifference(vector<int> A,vector<int> B){
    int n=A.size();
    int m=B.size();
    unordered_set<int> differenceSetA;
    unordered_set<int> differenceSetB;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            differenceSetA.insert(abs(A[i]-A[j]));
        }
    }
    for(int i=0;i<m;i++){
        for(int j=i+1;j<m;j++){
            differenceSetB.insert(abs(B[i]-B[j]));
        }
    }
    int count=0;
    for(auto &it:differenceSetA){
        if(differenceSetB.find(it)!=differenceSetB.end()){
            count++;
        }
    }
    return count;
    
}

请提供优化O(N log N)方法的建议。

Answer 1

如果n是输入数组的最大范围，则可以在O(n logn)中获得给定数组的所有差异集，如在SO post：find all differences in a array中所解释的那样。

这里简要回顾了该方法，并提供了一些其他实用的实现细节：

1. 创建一个长度为2*n = 2*range = 2*(Vmax - Vmin + 1)的数组Posi，其中索引与输入元素匹配的元素设置为1，其他元素设置为0。这可以在O(m)中创建，其中m是数组的大小。

例如，在大小为m的输入数组1,4,5中，我们创建了一个数组1，0，1，1.

Initialisation: Posi[i] = 0 for all i (i = 0 to 2*n)
Posi[A[i] - Vmin] = 1 (i = 0 to m)

1. 计算了阵列Posi[]的自相关函数。这可以在三个子步骤(

)中经典地执行。

2.1计算Posi[]阵列的FFT (尺寸2*n)：Y[] = FFT(Posi)

2.2计算结果的平方振幅：Y2[k] = Y[k] * conj([Y[k])

2.3计算结果Diff[] = IFFT (Y2[])的逆FFT

有几个细节值得在此提及：

• 选择大小2*n的原因，而不是size n，如果是，则d是有效的差异，-d也是有效的差异。与负差异相对应的结果可以在i >= n
• If位置获得，您发现用a-幂为2的大小来执行快速傅立叶变换比用n2k >= 2*n

替换大小2*n更容易。

非空差异对应于数组Diff[]中的非空值。

`d` is a difference if `Diff[d] > 0`

另一个重要的细节是使用了一个经典的FFT (浮点计算)，然后你会遇到一些小的错误。考虑到这一点，重要的是将IFFT输出Diff[]替换为实部件的整数四舍五入值。

所有这一切只涉及一个数组。当您想要计算常见差异的数量时，您必须：

• 计算两个集合( A和B )的数组Diff_A[]和Diff_B[]，然后：

count = 0;
if (Diff_A[d] != 0) and (Diff_B[d] != 0) then count++;

小奖金

为了避免剽窃上述文章，这里有一个额外的解释，如何获得一个集合的差异，借助FFT。

输入数组A = {3, 6, 8}可以用以下z变换进行数学表示：

 A(z) = z^3 + z^6 + z^8 

然后，差分数组的相应z变换等于多项式乘积：

D(z) = A(z) * A(z*) = (z^3 + z^6 + z^8) (z^(-3) + z^(-6) + z^(-8)) 
= z^(-5) + z^(-3) + z^(-2) + 3 + z^2 + z^3 + z^5 

然后，我们可以注意到，A(z)等于序列[0 0 0 1 0 0 1 0 1]大小为N的FFT，方法是：

z = exp (-i * 2 PI/ N), with i = sqrt(-1)

注意，这里我们考虑了C中的经典FFT，复场。

当然可以在Galois字段中执行计算，然后不存在舍入误差，例如，对大量数字实现“经典”乘法(z= 10)。这看起来太熟练了。