找出排序数组中具有相同差异的夫妻数量

Question

这是一个面试问题.

"给定一个排序的数组.找出具有相同差异的夫妻数量."

例如:if array是{1,2,3,5,7,7,8,9};

然后我们有

5对,差异为1

6对,差异为2

4对,相差4

2对,差3

4对,相差6

3对差异为5

2对,差异为7

1对,相差8

1对,差异为0

我尝试了以下方法:

maxdiff=arr[n-1]-arr[0];  //calculating the maximum difference
int b[maxdiff];
for(i=0;i<maxdiff;i++)
{
 for(j=0;j<n;j++)
 {
  p=arr[j]+i;
  x=binarysearch(p,arr);    //search p in array,where x return 0/1
  if(x==1)
  b[i]++;
 }
}

这是O(k*n*logn)解决方案,其中k是排序数组的第一个和最后一个元素之间的最大差异,n是数组大小.

有没有人有比这更好的主意？

Answer 1

这似乎不必要地复杂,我不完全看到你在做什么.问题是否仅通过以下方式解决:

maxdiff=arr[n-1]-arr[0];  //calculating the maximum difference
int b[maxdiff];
for(i=0;i<n;i++)
{
   for(j=0;j<i;j++) // note: <i instead of <n
   {
      b[arr[i]-arr[j]]++
   }
}

这是O(n**2).

顺便说一句,你没有列出一对差异为8或一对差异为0.有意吗？

编辑:

逻辑就是:查看原始数组中的每一对.每对形成差异.为这种差异增加计数器.

编辑2:

根据您的要求,以下是我的测试结果:

C:\src>a
diff: 0 pairs: 1
diff: 1 pairs: 5
diff: 2 pairs: 6
diff: 3 pairs: 2
diff: 4 pairs: 4
diff: 5 pairs: 3
diff: 6 pairs: 4
diff: 7 pairs: 2
diff: 8 pairs: 1

以及完整的计划:

#include <iostream>
using namespace std;

int main (int argc, char *argv[])
{
  int n=8;
  int arr[] = {1,2,3,5,7,7,8,9};
  int i, j;

  int maxdiff=arr[n-1]-arr[0];  //calculating the maximum difference
  int b[maxdiff];

  for(i=0;i<=maxdiff;i++)
    {
      b[i]=0;
    }  

  for(i=0;i<n;i++)
    {
      for(j=0;j<i;j++) // note: <i instead of <n
        {
          b[arr[i]-arr[j]]++;
        }
    }

  for (i=0;i<=maxdiff;++i)
    cout<<"diff: "<<i<<" pairs: "<<b[i]<<endl;
}

Answer 2

如果使用傅里叶变换进行多项式的乘法,则可以在O(k*log k)(其中k是最大差)中求解.

考虑以下问题:有两组A = a_1,...,a_n和B = b_1,...,b_m,对于每个X找到对(i,j)的数量,使得a_i + b_j = X.可以解决如下.

设Pa = x**a_1 + ... + x**a_n,Pb = x**b_1 + ... + x**b_m.如果你看一下Pa*Pb,你可能会发现x**R的系数是X = R的问题的答案.所以,使用傅里叶变换乘以这个多项式,你会找到O中每个X的答案. (n*log n).

之后,你的问题可能会减少到这个问题,说A = arr_1,...,arr_n,B = -arr_1,...,-arr_n和移位(加一个常数)到A和B的每个值,使它们成为介于0和k之间.