Valor majoritário
A missão
Problema
Um valor de uma lista ocupa mais da metade de todas as posições. Retorne esse valor. Você pode assumir que esse valor sempre existe, então nunca precisa informar falha, e a lista nunca é vazia.
Exemplos
Input: nums = [3, 3, 4]
Output: 3
Por quê: 3 ocupa dois dos três slots, o que é mais da metade
Input: nums = [2, 2, 1, 1, 2]
Output: 2
Por quê: o valor majoritário não precisa estar agrupado
Input: nums = [9]
Output: 9
Por quê: edge case: o único valor ocupa, trivialmente, mais da metade da lista
Dicas
0 / 3
Contar cada valor em um mapa resolve, mas a garantia de que um valor ocupa mais da metade dos slots é um fato muito mais forte do que uma contagem completa exige.
Imagine cada ocorrência do valor majoritário anulando uma ocorrência de outro valor. Como ele ocupa mais da metade, sempre sobra alguma coisa depois das anulações.
Carregue um candidato atual e um contador de vantagem. Quando a vantagem chegar a zero, adote o elemento atual como novo candidato. Aumente a vantagem quando o elemento for igual ao candidato e diminua caso contrário. O candidato que restar no final é a resposta.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- one value fills more than half the positions
- the list is never empty
Solução
Parear cada ocorrência da maioria com uma ocorrência de outro valor anula as duas, e, como a maioria ocupa mais da metade dos slots, ela não pode ser anulada por completo. Um único candidato e um contador de vantagem simulam esse pareamento sem guardar mais nada: a vantagem chegar a zero significa que o candidato anterior foi totalmente pareado, então o próximo elemento começa uma nova rodada. O tempo é O(n), com uma passada, e o espaço é 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])) # -> 9Travou na ideia, e não no código? Majority Element explica isso.