Leetcode 150 | Giorno 4: Majority Element
Leetcode 169 ti chiede di trovare l'elemento di maggioranza in un array. L'elemento di maggioranza appare più di n / 2 volte. Assumiamo che esista sempre.
Puoi risolverlo in due modi.
Approccio 1: Il metodo Map
Questo metodo utilizza una Map per contare quante volte appare ogni numero.
- Crea una Map per memorizzare i conteggi.
- Cicla attraverso l'array.
- Aggiorna il conteggio per ogni numero.
- Cicla attraverso la Map per trovare il numero con un conteggio superiore a n / 2.
Complessità:
- Tempo: O(n) perché utilizzi due cicli sequenziali.
- Spazio: O(n) perché la Map cresce con il numero di elementi univoci.
Approccio 2: Algoritmo di voto di Boyer-Moore
Questo è un modo ottimizzato per risolvere il problema utilizzando una memoria costante.
Pensa ai numeri come a squadre avversarie. Ogni volta che un numero incontra un numero diverso, si annullano a vicenda. Poiché l'elemento di maggioranza appare più della metà delle volte, sarà sempre l'ultimo a rimanere in piedi.
Come funziona:
- Scegli un candidato e imposta un conteggio a 0.
- Cicla attraverso l'array.
- Se il conteggio è 0, imposta il numero corrente come candidato.
- Se il numero corrente corrisponde al candidato, aumenta il conteggio di 1.
- Se non corrisponde, diminuisci il conteggio di 1.
Complessità:
- Tempo: O(n) perché attraversi l'array una sola volta.
- Spazio: O(1) perché utilizzi solo due variabili.
Perché è importante:
Entrambi i metodi hanno una complessità temporale di O(n). Tuttavia, il secondo approccio utilizza molta meno memoria. Non ha bisogno di una Map. Questo lo rende migliore per dataset di grandi dimensioni.
Fonte: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6