効率的なアルゴリズムを提案する

Question

配列arrのサイズが100000の場合、各要素は0 <= arr[i] < 100となります。

は(i,j,k)が存在しているどのように多くのトリプレットを調べる（ソートされていない、重複が含まれている）ようにarr[i]^arr[j]^arr[k] == 0 注：^は、XOR演算子ですが。また0 <= i <= j <= k <= 100000

私は周波数を計算し、周波数を使って計算をしなければならないと感じていますが、私はちょうど始められないようです。

明白なO(n^3)より優れたアルゴリズムは歓迎します。 :)

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

Answer 1

私は、キーはあなたがどのように多くのI、J、K、ただ数える指定する必要はありませんだと思います。トリプルどのワークアウト、小さな配列の非零要素をO（N）

ループ -

ある何各値のカウント、しかしARRアレイサイズ100

ループを初期化条件を満たす - 3つの数のカウントがA、B、Cであると仮定する - 元のarrの組み合わせの数は（A + B + C）/！A！B！C！ - 100 ** 3の演算ですが、100が固定値であると仮定してもO（1）です。

したがって、O（n）。

Answer 2

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）

Answer 3

可能な場合、O（n^2）の可能な解決策：変数countと2つの配列single[100]とpair[100]を維持します。 arr、値nの各要素についての反復：

• 更新count：count += pair[n]
• 更新pair：single[n]++：反復配列singleインデックスx値s != 0の各要素のためにpair[s^n] += single[x]
• 更新singleを行います

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

Answer 4

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

次に、その配列からトリプルA、B、Cをループし、条件A^B^C = 0をテストする代わりに、 A < B.各A、Bについて、C = A^Bを計算して（今度はA^B^C = 0となるように）、A < B < C < 100を検証します（何らかの順序でこれはトリプルを見逃しませんが、以下を参照してください）。実行中の合計は次のようになります。

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

作業は3つの異なる番号のすべてのトリプル以来< B.

をループするための周波数のカウントのためのO（n）は、プラス約5000でありますA、B、Cは何らかの順序で出現しなければならない。次に、2つの数字が等しいトリプルを探す必要があります。しかし、2つの数が等しく、3つのxorが0の場合、3番目の数はゼロでなければなりません。したがって、これは、（A = 0、B = C < 100）の出現をカウントして、頻度カウントアレイ上のBの2次線形検索になります。 （この場合、特にB = 0の場合に注意してください。数は周波数[B] ** 2または周波数[0] ** 3だけではありません）3.コンビナトリアルの問題が隠れています。

希望します。

Answer 5

可能な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; 
} 

...

Answer 6

私は（シンプル）はO（n^2ログn）を持っていますi、j、kが整数ではなく指数を参照するという事実を考慮した解。

単純な最初のパスでは、100個の値の配列Aを作成することができます。値 - >インデックスのリスト。私たちは後で使用するために並べ替えられたリストを保持します。 O（n log n）

i < = jとなる各ペアiについて、X = arr [i]^arr [j]を計算する。次に、A> [X]で2分探索を実行して、k> = jとなるようなインデックスkの数を突き止める。 O（n^2 log n）

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