c++ - 共同差异数

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 帖子中所述:find all differences in a array

这里是对该方法的简要回顾，以及一些额外的实际实现细节:

1. Create an array Posi of length 2*n = 2*range = 2*(Vmax - Vmin + 1), where elements whose index matches an element of the input are set to 1, other elements are set to 0. This can be created in O(m), where m is the size of the array.
   For example, given in input array [1,4,5] of size m, we create an array [1,0,0,1,1].

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

2. Calculate the autocorrelation function of array Posi[]. This can be classically performed in three sub-steps

2.1 Calculate the FFT (size 2*n) of Posi[]array: Y[] = FFT(Posi)

2.2 Calculate the square amplitude of the result: Y2[k] = Y[k] * conj([Y[k])

2.3 Calculate the Inverse FFT of the result Diff[] = IFFT (Y2[])`

这里有几个细节值得一提:

• 选择尺寸 2*n 而不是尺寸 n 的原因是 d 是有效的区别, 那么 -d 也是一个有效的区别。负差异对应的结果可在位置 i >= n
获得
• 如果您发现使用大小的二次幂更容易执行 FFT，则可以将大小 2*n 替换为值 n2k = 2^k，n2k >= 2*n

3. The non-null differences correspond to non-null values in the array Diff[]:

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

另一个重要的细节是使用了经典的 FFT(浮点计算)，那么您几乎不会遇到错误。考虑到这一点，重要的是用实部的整数舍入值替换 IFFT 输出 Diff[]。

所有这些只涉及一个数组。由于要计算公差数，则必须:

• calculate the arrays Diff_A[] and Diff_B[] for both sets A and B and then:

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，即复数域。

当然有可能在伽罗华域中执行计算，然后没有舍入误差，例如为大量数字实现“经典”乘法(z = 10)。这在这里似乎过于熟练了。