8

これはインタビューの質問です。

「ソートされた配列が与えられました。同じ差を持つカップルの数を見つけてください。」

例: 配列が {1, 2, 3, 5, 7, 7 , 8, 9} の場合。

それから私たちは持っています

差が 1 の 5 つのペア

2の差で6ペア

4 の差がある 4 つのペア

3 の差がある 2 つのペア

6 の差がある 4 つのペア

5 の差がある 3 つのペア

7 の差がある 2 つのペア

8の差で1ペア

差が0の1ペア

私は次のことを試しました：

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 の 1 つのペアまたは差が 0 の 1 つのペアをリストしませんでした。わざとですか?

編集：

ロジックは単純です: 元の配列の各ペアを見てください。各ペアが違いを形成します。その差のカウンターを増やします。

編集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 は最大差) で解決できます。

次の問題を考えてみましょう: X ごとに A = a_1, ..., a_n と B = b_1, ..., b_m という 2 つのセットを持ち、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 に答える