Valor mayoritario
La misión
Problema
Un valor de una lista ocupa más de la mitad de todas las posiciones. Devuelve ese valor. Puedes suponer que ese valor siempre existe, así que nunca tienes que informar un fallo, y la lista nunca está vacía.
Ejemplos
Input: nums = [3, 3, 4]
Output: 3
Por qué: 3 ocupa dos de las tres casillas, lo que es más de la mitad
Input: nums = [2, 2, 1, 1, 2]
Output: 2
Por qué: el valor mayoritario no tiene que estar agrupado
Input: nums = [9]
Output: 9
Por qué: caso límite: el único valor ocupa trivialmente más de la mitad de la lista
Pistas
0 / 3
Contar cada valor en un diccionario lo resuelve, pero la garantía de que un valor ocupa más de la mitad de las casillas es un dato mucho más fuerte de lo que necesita un conteo completo.
Imagina que cada aparición del valor mayoritario cancela una aparición de otro valor. Como ocupa más de la mitad, siempre sobrevive algo a la cancelación.
Lleva un candidato actual y un contador de ventaja. Cuando la ventaja llegue a cero, adopta el elemento actual como nuevo candidato. Sube la ventaja cuando el elemento coincida con el candidato y bájala en caso contrario. El candidato que queda en pie al final es la respuesta.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Restricciones
- one value fills more than half the positions
- the list is never empty
Solución
Emparejar cada aparición del valor mayoritario con una aparición de otro valor cancela ambas, y como el mayoritario ocupa más de la mitad de las casillas, no puede cancelarse por completo. Un solo candidato más un contador de ventaja simula ese emparejamiento sin guardar nada más: que la ventaja llegue a cero significa que el candidato anterior quedó totalmente emparejado, así que el siguiente elemento empieza una ronda nueva. El tiempo es O(n) con una sola pasada, y el espacio es O(1).
def majority_value(nums):
candidate = None
lead = 0 # how far the candidate is ahead
for x in nums:
if lead == 0: # the previous candidate was fully cancelled
candidate = x
lead += 1 if x == candidate else -1
return candidate
print(majority_value([3, 3, 4])) # -> 3
print(majority_value([2, 2, 1, 1, 2])) # -> 2
print(majority_value([9])) # -> 9¿Lo que te frena es la idea y no el código? Majority Element lo explica.