Ein bisschen alte algorithmische Magie oder das Lösen einer faszinierenden Abfolge von Aufgaben mit LeetCode

Vor einiger Zeit bin ich auf der Website leetcode.com auf eine amüsante Aufgabenreihe gestoßen. Die Aufgaben selbst sind nicht allzu schwierig, aber ihre Lösungen sind durchaus faszinierend. Darüber hinaus tauchen Probleme dieser Art häufig in Vorstellungsgesprächen bei großen Unternehmen auf, und das Verständnis der Methoden zu ihrer Lösung kann sehr hilfreich sein.

Die erste Aufgabe ist 136. Einzelne Zahl (einfach)

Bei einem nicht leeren Array von Ganzzahlen, in dem jedes Element bis auf eines zweimal vorkommt, müssen Sie das Element ohne Paar finden. Lösen Sie das Problem in O(n)-Zeitkomplexität und mit konstantem zusätzlichem Speicher.

Beispiel 1:

Eingabe: nums = [1, 3, 3, 2, 6, 2, 1]

Ausgabe: 6

Beispiel 2:

Eingabe: nums = [12, 1, 1, 7, 1, 12, 1]

Ausgabe: 7

Beispiel 3:

Eingabe: nums = [6]

Ausgabe: 6

Wir nutzen die XOR-Funktionseigenschaft, die nur dann 1 ergibt, wenn ihre Operanden unterschiedlich sind. Indem wir alle Elemente des Arrays durchlaufen und eine bitweise XOR-Verknüpfung für sie durchführen, werden alle identischen Bitwerte auf Null gesetzt. Als Ergebnis bleibt das gewünschte Ergebnis übrig.

Hier ist ein kurzer Python3-Lösungscode:

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

Wir verwenden nur so viel zusätzlichen Speicher, wie eine Ganzzahl belegt, und finden die Lösung in einem einzigen Durchgang durch das gegebene Array, was uns eine O(n)-Komplexität verleiht. Dies ist eine prägnante und elegante Lösung.

Das zweite Problem ist 137. Einzelne Zahl II (mittlerer Schwierigkeitsgrad)

Bei einem nicht leeren Array von Ganzzahlen, in dem jedes Element bis auf eines dreimal vorkommt und nur ein Element einmal vorkommt, müssen wir dieses eindeutige Element finden. Lösen Sie das Problem in O(n)-Zeitkomplexität und mit konstantem zusätzlichem Speicher.

Beispiel 1:

Eingabe: nums = [3, 1, 3, 3]

Ausgabe: 1

Beispiel 2:

Eingabe: nums = [12, 1, 1, 5, 1, 12, 12]

Ausgabe: 5

Beispiel 3:

Eingabe: nums = [6]

Ausgabe: 6

Leider können wir in diesem Fall den vorherigen Trick nicht anwenden, da wir gepaarte Bits an der erforderlichen Position nicht in Nullen umwandeln können. Es wäre verlockend, das gegebene Array in das Format der vorherigen Aufgabe umzuwandeln und es dann auf ähnliche Weise zu lösen.

Wenn wir auf diese Weise argumentieren, ist es leicht zu erkennen, dass wir der Summe, die wir erhalten, ein zusätzliches XOR mit N hinzufügen könnten, wenn wir wüssten, dass wir beim Durchlaufen des Arrays bereits zweimal (oder dreimal) auf die Zahl N gestoßen sind. Dies würde das endgültige XOR mit dieser Zahl gerade machen und sie dadurch aus der Endsumme entfernen, und was übrig bliebe, wäre unsere Antwort.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

Leider würde diese Lösung maximal (len(nums)-1)/3 an Speicher erfordern, was nicht als konstanter Verbrauch angesehen werden kann, sodass wir nach einer anderen Lösung suchen müssen.

Versuchen wir, unseren Ansatz zu ändern.

Früher haben wir XOR verwendet (was die Addition Modulo 2 darstellt). Wenn wir die Addition Modulo 3 implementiert hätten, hätten wir den Trick aus dem vorherigen Beispiel problemlos anwenden können.

Wenn wir beim ersten Mal, wenn wir darauf stoßen, eine Zahl in die Antwort einfügen, sie beim zweiten Mal in den Akkumulator einfügen und beim dritten Mal sowohl die Antwort als auch den Akkumulator auf Null setzen können, würde uns das helfen, das Problem in einem Durchgang zu lösen Die Liste mit zusätzlichem Speicherverbrauch entspricht genau zwei Ganzzahlen und erfüllt die Aufgabenanforderungen.

Lassen Sie uns also etwas mehr bitweise Magie anwenden:

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

Auf diese Weise werden alle Tripelzahlen auf Null gesetzt und uns bleibt nur die Zahl übrig, die nur einmal vorkommt.

Die dritte Aufgabe ist 260. Einzelnummer III (mittlerer Schwierigkeitsgrad)

Bei einem nicht leeren Array von Ganzzahlen, in dem jedes Element zweimal vorkommt, mit Ausnahme von zwei Elementen, die nur einmal vorkommen, müssen wir diese eindeutigen Elemente finden. Das Ziel besteht darin, das Problem in O(n)-Zeitkomplexität und mit konstantem zusätzlichem Speicher zu lösen, wobei die Reihenfolge der eindeutigen Elemente keine Rolle spielt.

Beispiel 1:

Eingabe: nums = [1, 2, 1, 3, 2, 5]

Ausgabe: [3, 5]

Beispiel 2:

Eingabe: nums = [1, -2]

Ausgabe: [-2, 1]

Offensichtlich können wir mit der XOR-Operation ganz einfach alle gepaarten Zahlen eliminieren, wie wir es bei der Lösung der ersten Aufgabe getan haben. Die Komplexität der Aufgabe besteht dann darin, eine der eindeutigen Zahlen zu identifizieren. Anschließend kann die zweite einfach durch XOR-Verknüpfung mit unserer XOR-Summe berechnet werden.

Um dies zu erreichen, müssen wir lediglich die unterschiedlichen Bits zwischen diesen eindeutigen Zahlen finden. Dann durchlaufen wir das Array erneut, führen eine XOR-Summierung durch und teilen die Ergebnisse in zwei Gruppen auf – für Zahlen, bei denen dieses Bit gesetzt ist, und für diejenigen, bei denen es 0 ist. Als Ergebnis erhalten wir die gewünschten eindeutigen Elemente.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

Obwohl das Array zweimal durchlaufen werden muss, bleibt die Komplexität O(n) und der Speicherverbrauch beträgt nur 2 ganze Zahlen.

Hinweis: Obwohl int in Python nicht genau mit int in anderen Sprachen übereinstimmt, betrachten wir seine Größe als Konstante