共同明显差异的数量 [英] Numbers of common distinct difference

问题描述

给出两个数组A和B.查找共同不同的数量(两个数组中元素的差)的任务.例子:

  A = [3,6,8]B = [1,6,10]所以我们得到A的differenceSetDifferenceSetA = [abs(3-6)，abs(6-8)，abs(8-3)] = [3,5,2]相似地DifferenceSetB = [abs(1-6)，abs(1-10)，abs(6-10)] = [5,9,4]公用元素数=交集:{differenceSetA，differenceSetB} = {5}答案= 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(自动& it:differenceSetA){if(differenceSetB.find(it)！= differenceSetB.end()){数++;}}返回计数；} 

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

解决方案

如果n是输入数组的最大范围，则可以在O(n logn)中获得给定数组的所有差的集合，如所解释的在此SO帖子中:

计算数组 Posi [] 的自相关函数.传统上，这可以分为三个子步骤

2.1计算 Posi [] 数组的FFT(大小2 * n): Y [] = FFT(Posi)

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

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

一些细节值得在这里提及:

• 选择大小为 2 * n 而不选择大小为 n 的原因是 d ，这是有效的区别，则 -d 也是有效的区别.负差对应的结果可在 i> = n
的位置获得
• 如果您发现大小为a的2的幂的FFT更容易执行，则可以将大小 2 * n 替换为值 n2k = 2 ^ k ，其中 n2k> = 2 * n

3. 非null差异对应于 Diff [] 数组中的非null值:

如果`Diff [d]>0`

另一个重要的细节是使用经典的FFT(浮点计算)，因此您遇到的错误很小.考虑到这一点，重要的是用实部的整数舍入值替换IFFT输出 Diff [] .

所有仅涉及一个数组.要计算共同差异的数量，则必须:

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

  count = 0;如果(Diff_A [d]！= 0)和(Diff_B [d]！= 0)，则计算++； 

---

一点奖金

为了避免抄袭该帖，这里是有关借助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)，其中i = sqrt(-1) 

请注意，这里我们考虑C中的经典FFT，即复数域.

当然有可能在Galois字段中执行计算，然后没有舍入错误，因为例如可以实现经典"运算.大量数字的乘法(z = 10).这似乎在这里太熟练了.

Given two array A and B. Task to find the number of common distinct (difference of elements in two arrays). Example :

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

My approach 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;
    
}

Please provide suggestions for optimizing the approach in O(N log N)

解决方案

If n is the maximum range of a input array, then the set of all differences of a given array can be obtained in O(n logn), as explained in this SO post: find all differences in a array

Here is a brief recall of the method, with a few additional practical implementation details:

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[])`

A few details are worth being mentioned here:

• The reason why a size 2*n was selected, and not a size n, if that, is d is a valid difference, then -d is also a valid difference. The results corresponding to negative differences are available at positions i >= n
• If you find more easy to perform FFT with a size a-power-of-two, than you can replace the size 2*n with a value n2k = 2^k, with 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`

Another important details is that a classical FFT is used (float calculations), then you encounter little errors. To take it into account, it is important to replace the IFFT output Diff[] with integer rounded values of the real part.

All that concerns one array only. As you want to calculate the number of common differences, then you have to:

• 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++;

---

A little Bonus

In order to avoid a plagiarism of the mentioned post, here is an additional explanation about the way to get the differences of one set, with the help of the FFT.

The input array A = {3, 6, 8} can mathematically be represented by the following z transform:

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

Then the corresponding z-transform of the difference array is equal to the polynomial product:

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 

Then, we can note that A(z) is equal to a FFT of size N of the sequence [0 0 0 1 0 0 1 0 1] by taking:

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

Note that here we consider the classical FFT in C, the complex field.

It is certainly possible to perform calculation in a Galois field, and then no rounding errors, as it is done for example to implement "classical" multiplications (with z = 10) for a large number of digits. This seems over-skilled here.

这篇关于共同明显差异的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！