𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝘆 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 verlangt von Ihnen, das Majority Element in einem Array zu finden. Das Majority Element erscheint mehr als n / 2 Mal. Wir gehen davon aus, dass es immer existiert.
Sie können dies auf zwei Arten lösen.
Ansatz 1: Die Map-Methode
Diese Methode verwendet eine Map, um zu zählen, wie oft jede Zahl vorkommt.
- Erstellen Sie eine Map, um die Häufigkeiten zu speichern.
- Durchlaufen Sie das Array.
- Aktualisieren Sie die Anzahl für jede Zahl.
- Durchlaufen Sie die Map, um die Zahl mit einer Anzahl zu finden, die höher als n / 2 ist.
Komplexität:
- Zeit: O(n), da Sie zwei aufeinanderfolgende Schleifen verwenden.
- Speicher: O(n), da die Map mit der Anzahl der eindeutigen Elemente wächst.
Ansatz 2: Boyer-Moore Voting Algorithm
Dies ist eine optimierte Art, das Problem mit konstantem Speicher zu lösen.
Stellen Sie sich die Zahlen als gegnerische Teams vor. Jedes Mal, wenn eine Zahl auf eine andere Zahl trifft, heben sie sich gegenseitig auf. Da das Majority Element mehr als die Hälfte der Zeit vorkommt, wird es immer der Letzte sein, der übrig bleibt.
Funktionsweise:
- Wählen Sie einen Kandidaten und setzen Sie einen Zähler auf 0.
- Durchlaufen Sie das Array.
- Wenn der Zähler 0 ist, setzen Sie die aktuelle Zahl als Kandidaten.
- Wenn die aktuelle Zahl mit dem Kandidaten übereinstimmt, erhöhen Sie den Zähler um 1.
- Wenn sie nicht übereinstimmt, verringern Sie den Zähler um 1.
Komplexität:
- Zeit: O(n), da Sie das Array nur einmal durchlaufen.
- Speicher: O(1), da Sie nur zwei Variablen verwenden.
Warum das wichtig ist:
Beide Methoden haben eine Zeitkomplexität von O(n). Der zweite Ansatz verbraucht jedoch viel weniger Speicher. Er benötigt keine Map. Dies macht ihn besser für große Datensätze geeignet.
Quelle: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6