𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗮𝗴 𝟰: 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝘆 𝗘𝗹𝗲𝗺𝗲𝗻𝘁
Leetcode 169 vraagt je om het meerderheidselement in een array te vinden. Het meerderheidselement komt vaker dan n / 2 keer voor. We gaan ervan uit dat het altijd bestaat.
Je kunt dit op twee manieren oplossen.
Aanpak 1: De Map-methode
Deze methode gebruikt een Map om te tellen hoe vaak elk getal voorkomt.
- Maak een Map aan om de tellingen op te slaan.
- Loop door de array.
- Update de telling voor elk getal.
- Loop door de Map om het getal te vinden met een telling hoger dan n / 2.
Complexiteit:
- Tijd: O(n) omdat je twee opeenvolgende loops gebruikt.
- Ruimte: O(n) omdat de Map groeit met het aantal unieke elementen.
Aanpak 2: Boyer-Moore Voting Algorithm
Dit is een geoptimaliseerde manier om het probleem op te lossen met constant geheugen.
Zie de getallen als tegenovergestelde teams. Elke keer dat een getal een ander getal tegenkomt, heffen ze elkaar op. Omdat het meerderheidselement meer dan de helft van de tijd voorkomt, zal het altijd de laatste zijn die overblijft.
Hoe het werkt:
- Kies een kandidaat en stel een telling in op 0.
- Loop door de array.
- Als de telling 0 is, stel het huidige getal dan in als de kandidaat.
- Als het huidige getal overeenkomt met de kandidaat, verhoog de telling met 1.
- Als het niet overeenkomt, verlaag de telling met 1.
Complexiteit:
- Tijd: O(n) omdat je slechts één keer door de array loopt.
- Ruimte: O(1) omdat je slechts twee variabelen gebruikt.
Waarom dit belangrijk is:
Beide methoden hebben een tijdcomplexiteit van O(n). De tweede aanpak gebruikt echter veel minder geheugen. Er is geen Map voor nodig. Dit maakt het beter geschikt voor grote datasets.
Bron: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6