8

这是一个面试题。

“给定一个排序数组。找出具有相同差异的夫妇的数量。”

例如：如果数组是 {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 是数组大小。

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

4

3 回答 3

7

它似乎不必要地复杂，我不完全明白你在做什么。问题是否仅通过以下方式解决：

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;
}
于 2013-07-17T09:26:33.097 回答
5

如果您使用傅里叶变换进行多项式的乘法运算，这可以在 O(k*log k) 中解决（其中 k 是最大差） 。

考虑以下问题：有两个集合 A = a_1, ..., a_n 和 B = b_1, ..., b_m，对于每个 X，找到满足 a_i + b_j = X 的对 (i, j) 的数量。它可以如下解决。

设 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 之间。

于 2013-07-17T17:14:36.257 回答
1

对于一般输入数组，这不能比 O(n^2) 更好地解决，因为某些输入会导致 O(n^2) 不同的输出。例如，很容易构造一个数组，其中每对元素都有不同的分隔。

如果它询问具有特定分隔的对的数量，则该问题更有意义。这可以在线性时间内完成，并使用数组已排序的事实。如果我们能做的最好的事情是比排序慢，那么给出一个排序数组是没有意义的。

于 2013-07-17T20:23:00.840 回答