Algorithmen und Datenstrukturen · Middle · Frage 63 von 75
Jede Zahl in einem Array kommt zweimal vor, außer einer. Wie findet man sie in O(n) Zeit und O(1) Speicher?
- 1Die Vorkommen jeder Zahl in einer Hash-Map zählen
- 2Alles per XOR verknüpfen: Paare fallen weg, eine bleibt
- 3Das Array sortieren und benachbarte Werte vergleichen
Antwort zeigen
Richtige Antwort: Alles per XOR verknüpfen: Paare fallen weg, eine bleibt
Erklärung
a ^ a = 0 und a ^ 0 = a, und XOR ist kommutativ, Paare verschwinden also in jeder Reihenfolge. Sortieren ist O(n log n); eine Map ist O(n) Zeit, aber O(n) Speicher.