Schlagen Sie einen effizienten Algorithmus

Question

Da ein Array arr von Größe 100000, jedes Element 0 <= arr[i] < 100. (Nicht sortiert, enthält Duplikate)

Finden Sie heraus, wie viele Drillinge (i,j,k) vorhanden sind, so dass arr[i] ^ arr[j] ^ arr[k] == 0 Hinweis : ^ ist der Xor-Operator. auch 0 <= i <= j <= k <= 100000

Ich habe das Gefühl, ich muß die Frequenzen berechnen und eine Berechnung tun, um die Frequenz, aber ich kann einfach nicht loszulegen scheinen.

Jeder Algorithmus besser als der offensichtliche O(n^3) ist willkommen. :)

Es ist nicht Hausaufgaben. :)

Answer 1

Ich denke, der Schlüssel ist, dass Sie nicht identifizieren müssen, um das i, j, k, nur zählen, wie viele.

Initialise eine Array-Größe 100

Schleife obwohl arr, Zählen, wie viele der einzelnen Werte sind - O (n)

Schleife durch Nicht-Null-Elemente des kleinen Array, arbeiten heraus, was verdreifacht die Bedingung erfüllen - übernehmen die Zählungen der drei Zahlen sind beteiligt A, B, C - die Anzahl der Kombinationen in der ursprünglichen arr ist (A + B + C) /! A! B! C! - 100 ** 3 Operationen, aber das ist immer noch O (1) unter der Annahme der 100 einen festen Wert

.

So, O (n).

Answer 2

Mögliche O (n ^ 2) Lösung, wenn es funktioniert: Pflegen Variable count und zwei Arrays, single[100] und pair[100]. Iterate die arr, und für jedes Element Wert n:

• update count: count += pair[n]
• update pair: iterate Array single und für jedes Element von Index x und Wert s != 0 tun pair[s^n] += single[x]
• update single: single[n]++

Am Ende count hält das Ergebnis an.

Answer 3

Mögliches O (100 * n) = O (n) Lösung. es löst Problem i <= j <= k. Wie Sie wissen, A ^ B = 0 <=> A = B, so

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;
}

Sorry für mein schlechtes Englisch ...

Answer 4

Ich habe eine (einfache) O (n ^ 2 log n) Lösung, die berücksichtigt die Tatsache, dass i, j und k-Indizes beziehen, nicht ganze Zahlen sind.

Ein einfacher erster Durchgang ermöglicht es uns, ein Array A von 100 Werten aufzubauen: Werte -> Liste des Indizes, halten wir die Liste für eine spätere Verwendung sortierte. O (n log n)

Für jedes Paar i, j, so dass i <= j, wir berechnen X = arr [i] ^ arr [j]. Wir führen dann eine binäre Suche in A [X] die Anzahl der Indizes k zu finden, so dass k> = j. O (n ^ 2 log n)

Ich konnte keine Möglichkeit finden, Hebel Sortieranlagen / Zählen Algorithmus, weil sie den Index Anforderung vernichten.

Answer 5

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 6

Starten Sie mit einer Frequenz Zählung der Anzahl von Vorkommen jeder Zahl zwischen 1 und 100, wie Paulus vermuten läßt. Dies erzeugt einen Array freq [] mit einer Länge von 100.

Als nächstes werden anstelle von Schleifen über Tripel A, B, C von dem Array und die Prüfung der Bedingung A ^ B ^ C = 0 ist, Schleife über Paare A, B mit A

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

Die Arbeit ist O (n) für die Frequenzzahl, plus etwa 5000 für die Schleife über A

Da jeder Tripel von drei andere Zahlen A, B, C muss in einem bestimmten Reihenfolge auftreten, diese Funde jede solche triple genau einmal. Als Nächstes werden Sie für Tripel in der zwei Zahlen gleich sind aussehen müssen. Aber wenn zwei Zahlen gleich sind und die xor von drei von ihnen sind 0, muss die dritte Zahl Null sein. So dass diese Mengen zu einer sekundären, linearen Suche nach B über die Frequenz-Zählfeld, das Zählen von Vorkommen (A = 0, B = C <100). (Seien Sie sehr vorsichtig mit diesem Fall und besonders vorsichtig mit dem Fall B = 0. Die Zahl ist nicht nur freq [B] ** 2 oder freq [0] ** 3. Es gibt ein kleines Problem Kombinatorik versteckt es.)

Hope, das hilft!