时间戳

首页 > 解决方案 > 共同显着差异数

c++ - 共同显着差异数

问题描述

给定两个数组 A 和 B。任务找出共同的 distinct 数（两个数组中元素的差异）。例子 ：

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) 方法的建议

标签： c++algorithmdata-structuressetc++17

解决方案

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

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

  1. Posi创建一个长度数组2*n = 2*range = 2*(Vmax - Vmin + 1)，其中索引与输入元素匹配的元素设置为 1，其他元素设置为 0。这可以在 O(m) 中创建，其中m是数组的大小。
    例如，给定输入数组 [1,4,5] 的大小m，我们创建一个数组 [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)
  1. 计算数组的自相关函数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选择 size 而不是 size的原因n是d有效差异，那么-d也是有效差异。对应于负差异的结果在位置可用i >= n
  • 如果您发现使用大小为 2 的幂的 FFT 更容易执行 FFT，则可以将大小替换2*n为 value n2k = 2^k，n2k >= 2*n
  1. 非空差异对应于数组中的非空值Diff[]：
`d` is a difference if `Diff[d] > 0`

另一个重要的细节是使用经典的 FFT（浮点计算），然后您会遇到很少的错误。考虑到这一点，重要的是用Diff[]实部的整数舍入值替换 IFFT 输出。

所有这些都只涉及一个阵列。当您要计算共同差异的数量时，您必须：

  • 计算数组Diff_A[]和Diff_B[]两个集合A，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)等于序列的大小为 N 的 FFT，[0 0 0 1 0 0 1 0 1]采用：

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

请注意，这里我们考虑的是复杂域 C 中的经典 FFT。

当然可以在伽罗瓦域中执行计算，然后不会出现舍入错误，例如为大量数字实现“经典”乘法（z = 10）。这在这里似乎过于熟练了。

推荐阅读