𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗶𝗮 𝟰: 𝗘𝗹𝗲𝗺𝗲𝗻𝘁𝗼 𝗠𝗮𝗷𝗼𝗿𝗶𝘁á𝗿𝗶𝗼
O Leetcode 169 pede para você encontrar o elemento majoritário em um array. O elemento majoritário aparece mais de n / 2 vezes. Assumimos que ele sempre existe.
Você pode resolver isso de duas maneiras.
Abordagem 1: O Método do Map
Este método usa um Map para contar quantas vezes cada número aparece.
- Crie um Map para armazenar as contagens.
- Percorra o array.
- Atualize a contagem de cada número.
- Percorra o Map para encontrar o número com uma contagem maior que n / 2.
Complexidade:
- Tempo: O(n) porque você usa dois loops sequenciais.
- Espaço: O(n) porque o Map cresce com o número de elementos únicos.
Abordagem 2: Algoritmo de Votação de Boyer-Moore
Esta é uma maneira otimizada de resolver o problema usando memória constante.
Pense nos números como times opostos. Toda vez que um número encontra um número diferente, eles se anulam. Como o elemento majoritário aparece mais da metade das vezes, ele sempre será o último sobrevivente.
Como funciona:
- Escolha um candidato e defina uma contagem como 0.
- Percorra o array.
- Se a contagem for 0, defina o número atual como o candidato.
- Se o número atual for igual ao candidato, aumente a contagem em 1.
- Se não for igual, diminua a contagem em 1.
Complexidade:
- Tempo: O(n) porque você percorre o array apenas uma vez.
- Espaço: O(1) porque você usa apenas duas variáveis.
Por que isso é importante:
Ambos os métodos têm uma complexidade de tempo de O(n). No entanto, a segunda abordagem utiliza muito menos memória. Ela não precisa de um Map. Isso a torna melhor para grandes conjuntos de dados.
Fonte: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6