0

arrサイズ 100000の配列を指定すると、各要素0 <= arr[i] < 100. (ソートされていない、重複を含む)

Note :が Xor 演算子である(i,j,k)ようなトリプレットがいくつ存在するかを調べます。またarr[i] ^ arr[j] ^ arr[k] == 0 ^0 <= i <= j <= k <= 100000

周波数を計算し、周波数を使用して計算を行う必要があると感じていますが、始められないようです。

明らかなものよりも優れたアルゴリズムO(n^3)は大歓迎です。:)

宿題ではありません。:)

4

6 に答える 6

4

重要なのは、i、j、kを識別する必要はなく、数を数えるだけだと思います。

配列サイズ100を初期化します

各値がいくつあるかを数えて、arrをループします-O（n）

小さな配列のゼロ以外の要素をループして、どのトリプルが条件を満たすかを調べます-関係する3つの数値のカウントがA、B、Cであると仮定します-元のarrの組み合わせの数は（A + B + C ）/！A！B！C！-100 ** 3の操作ですが、100が固定値であると仮定すると、それでもO（1）です。

すぐ）。

于 2010-11-18T11:23:27.117 に答える
1

可能な O(100 * n) = O(n) ソリューション。問題 i <= j <= k を解決します。ご存じのとおり、A ^ B = 0 <=> A = B なので、

long long calcTripletsCount( const vector<int>& sourceArray )
{
  long long res = 0;
  vector<int> count(128);
  vector<int> countPairs(128);
  for(int i = 0; i < sourceArray.size(); i++)
  {
    count[sourceArray[i]]++; // count[t] contain count of element t in (sourceArray[0]..sourceArray[i]) 
    for(int j = 0; j < count.size(); j++)
      countPairs[j ^ sourceArray[i]] += count[j]; // countPairs[t] contain count of pairs p1, p2 (p1 <= p2 for keeping order) where t = sourceArray[i] ^ sourceArray[j]
    res += countPairs[sourceArray[i]]; // a ^ b ^ c = 0 if a ^ b = c, we add count of pairs (p1, p2) where sourceArray[p1] ^ sourceArray[p2] = sourceArray[i]. it easy to see that we keep order(p1 <= p2 <= i)
  }  
  return res;
}

私の悪い英語でごめんなさい...

于 2010-11-18T13:05:30.847 に答える
1

可能な O(n^2) ソリューション: 変数countと 2 つの配列を維持しsingle[100]、pair[100]. arrvalue の各要素に対して、 および を繰り返しますn。

  • 更新count:count += pair[n]
  • update pair: 配列singleを反復し、indexxと valueの各要素に対してs != 0dopair[s^n] += single[x]
  • 更新single:single[n]++

最後countに結果を保持します。

于 2010-11-18T11:49:45.737 に答える
0 
Sort the array, keeping a map of new indices to originals. O(nlgn)
Loop over i,j:i<j. O(n^2)
  Calculate x = arr[i] ^ arr[j]
  Since x ^ arr[k] == 0, arr[k] = x, so binary search k>j for x. O(lgn)
  For all found k, print mapped i,j,k

O（n ^ 2 lgn）

于 2010-11-18T11:18:52.590 に答える
0

i、j、およびkが整数ではなくインデックスを参照するという事実を考慮した（単純な）O（n ^ 2 log n）ソリューションがあります。

単純な最初のパスで、100 個の値の配列 A を作成できます: 値 -> インデックスのリスト。後で使用するためにリストをソートしておきます。O(n log n)

i <= j となる各ペア i,j について、X = arr[i]^arr[j] を計算します。次に、A[X] でバイナリ検索を実行して、k >= j となるインデックス k の数を見つけます。O(n^2 log n)

並べ替え/カウント アルゴリズムを活用する方法が見つかりませんでした。これは、インデックスの要件を全滅させるためです。

于 2010-11-18T15:30:09.163 に答える
0

ポールが示唆するように、1 から 100 までの各数値の出現回数の頻度カウントから始めます。これにより、長さ 100 の配列 freq[] が生成されます。

次に、その配列からトリプル A、B、C をループして条件 A^B^C=0 をテストする代わりに、A < B のペア A、B をループします。各 A、B について、C=A^B を計算します。 (今は A^B^C=0)、A < B < C < 100 であることを確認してください。現在の合計は次のようになります。

Sum+=freq[A]*freq[B]*freq[C]

作業は、頻度カウントの O(n) と、A < B のループの約 5000 です。

3 つの異なる数値 A、B、C のすべてのトリプルは何らかの順序で発生する必要があるため、このような各トリプルは 1 回だけ検出されます。次に、2 つの数が等しいトリプルを探す必要があります。しかし、2 つの数値が等しく、そのうちの 3 つの xor が 0 の場合、3 番目の数値はゼロでなければなりません。したがって、これは、(A=0、B=C < 100) の出現をカウントして、頻度カウント配列に対する B の 2 次線形検索になります。(このケースには非常に注意してください。B=0 のケースには特に注意してください。カウントは、単に freq[B] ** 2 または freq[0] ** 3 ではありません。そこには、組み合わせ論の問題が少し隠れています。)

お役に立てれば！

于 2010-11-18T13:05:22.907 に答える