𝗟𝗲𝗲𝘁𝗰𝗼𝗱𝗲 𝟭𝟱𝟬 | 𝗗𝗶𝗮 𝟰: 𝗘𝗹𝗲𝗺𝗲𝗻𝘁𝗼 𝗠𝗮𝗷𝗼𝗿𝗶𝘁𝗮𝗿𝗶𝗼
Leetcode 169 te pide encontrar el elemento mayoritario en un arreglo. El elemento mayoritario aparece más de n / 2 veces. Asumimos que siempre existe.
Puedes resolver esto de dos maneras.
Enfoque 1: El método del Mapa
Este método utiliza un Mapa para contar cuántas veces aparece cada número.
- Crea un Mapa para almacenar los conteos.
- Recorre el arreglo.
- Actualiza el conteo de cada número.
- Recorre el Mapa para encontrar el número con un conteo superior a n / 2.
Complejidad:
- Tiempo: O(n) porque utilizas dos bucles secuenciales.
- Espacio: O(n) porque el Mapa crece con el número de elementos únicos.
Enfoque 2: Algoritmo de votación de Boyer-Moore
Esta es una forma optimizada de resolver el problema utilizando memoria constante.
Imagina que los números son equipos opuestos. Cada vez que un número se encuentra con un número diferente, se anulan entre sí. Dado que el elemento mayoritario aparece más de la mitad de las veces, siempre será el último en quedar en pie.
Cómo funciona:
- Elige un candidato y establece un conteo en 0.
- Recorre el arreglo.
- Si el conteo es 0, establece el número actual como el candidato.
- Si el número actual coincide con el candidato, aumenta el conteo en 1.
- Si no coincide, disminuye el conteo en 1.
Complejidad:
- Tiempo: O(n) porque solo recorres el arreglo una vez.
- Espacio: O(1) porque solo utilizas dos variables.
Por qué es importante:
Ambos métodos tienen una complejidad de tiempo de O(n). Sin embargo, el segundo enfoque utiliza mucha menos memoria. No necesita un Mapa. Esto lo hace mejor para conjuntos de datos grandes.
Fuente: https://dev.to/afuji/leetcode-150-day-4-majority-element-naive-vs-optimized-eo6