Majority Element
Você recebe um array de inteiros nums de comprimento n. Um valor aparece nele mais de n / 2 vezes, e esse valor é chamado de elemento majoritário. Retorne-o. Um valor que ocupa mais da metade do array é sempre único, então há exatamente uma resposta.
Função
- numsinteger-array
- o array de inteiros, com um valor ocupando mais da metade dele
- Retornainteger
- o valor que aparece mais de n / 2 vezes
Restrições
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- Um valor aparece mais de
nums.length / 2vezes.
Exemplos
- Entrada
- nums = [3, 9, 3, 3, 4]
- Saída
- 3
- Explicação
- 3 aparece três vezes em cinco elementos. Três é mais do que 5 / 2 = 2.5, e 9 e 4 aparecem uma vez cada.
- Entrada
- nums = [8, 8, 1, 1, 8, 1, 8]
- Saída
- 8
- Explicação
- 8 aparece quatro vezes e 1, três vezes. Sete elementos precisam de mais de 3.5 cópias, então 8 é a maioria, embora os 1s acompanhem o ritmo dele durante a maior parte do array.
Para ir além
Você consegue encontrar todos os valores que aparecem mais de n / 3 vezes, em O(n) de tempo e com O(1) de memória extra?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Contar cada valor funciona, mas exige memória extra. O que torna o valor majoritário especial? Compare quantas vezes ele aparece com quantas vezes todos os outros valores aparecem juntos.
Associe cada cópia do elemento majoritário a um valor diferente e risque ambos. O elemento majoritário supera todos os demais em quantidade, então algumas de suas cópias sobrevivem a qualquer associação desse tipo.
Mantenha um candidato e um contador. Some 1 quando um elemento corresponder ao candidato e subtraia 1 quando não corresponder. Quando o contador for 0, o próximo elemento se torna o candidato. O candidato que restar no final é a resposta.
Solução
A maioria supera todos os outros valores somados. Risque pares de valores diferentes, e algumas de suas cópias sempre sobrevivem. A votação de Boyer-Moore faz esse pareamento em uma única passagem, com um candidato e um contador, então você não precisa de um mapa hash de contagens.
Contagem com uma tabela hash
Intuição
Conte cada valor em um mapa hash e retorne o primeiro valor cuja contagem ultrapasse metade do comprimento. Para [3, 9, 3, 3, 4], a contagem de 3 chega a 3 no índice 3, mais do que 2.5, então você retorna antes de ler o 4.
cada consulta é O(1) em média, então o tempo é O(n), mas o mapa pode armazenar cerca de n / 2 valores diferentes: memória O(n).
Algoritmo
- Crie um mapa vazio de valores para contagens.
- Para cada elemento
x, adicione 1 à contagem dex. - Se essa contagem multiplicada por 2 for maior que o comprimento do array, retorne
x.
def majorityElement(nums):
counts = {}
for x in nums:
counts[x] = counts.get(x, 0) + 1
if counts[x] * 2 > len(nums):
return xVotação de Boyer-Moore
Intuição
Mantenha um candidate e um count dos votos dele que ainda não foram cancelados. Um elemento igual ao candidato adiciona um voto. Um elemento diferente cancela um voto, e ambos saem da disputa. Quando a contagem chega a 0, o próximo elemento se torna o candidato.
Cada cancelamento remove dois valores diferentes, portanto, no máximo, uma cópia do elemento majoritário. Se o elemento majoritário aparece m vezes, os outros n - m elementos são menos numerosos que m e não podem cancelar todas as cópias. Todos os votos restantes no final pertencem ao candidato final, e uma cópia do elemento majoritário está entre eles.
Em [8, 8, 1, 1, 8, 1, 8], a contagem vai de 1 para 2, depois para 1 e 0, enquanto os 1s cancelam os dois 8s. O próximo 8 reinicia a contagem em 1, o próximo 1 o cancela, e o último 8 se torna o candidato novamente. Uma passagem com duas variáveis leva tempo O(n) e usa memória O(1).
Algoritmo
- Defina
candidatecomo o primeiro elemento ecountcomo 0. - Para cada elemento
x, secountfor 0, tornexo candidato. - Se
xfor igual ao candidato, some 1 acount. Caso contrário, subtraia 1. - Após o último elemento, retorne
candidate.
def majorityElement(nums):
candidate = nums[0]
count = 0
for x in nums:
if count == 0:
candidate = x # the old candidate's votes are used up
if x == candidate:
count += 1
else:
count -= 1 # x and one copy of the candidate cancel out
return candidate
Armadilhas e casos extremos
- "Mais da metade" é estrito.
count >= n / 2aceita 2 cópias em 4, o que não é maioria. Comparecount * 2 > ne nenhum arredondamento atrapalha. - Ler o
countfinal como a frequência do elemento majoritário. Para[8, 8, 1, 1, 8, 1, 8], ele termina em 1, enquanto 8 aparece quatro vezes. - Começar com
candidate = nums[0]ecount = 1e, em seguida, percorrer a partir do índice 0. O primeiro elemento vota duas vezes: em[1, 2, 2], ocounttermina em 0 e você retorna 1.
Perguntas frequentes3
Qual é a complexidade de tempo e espaço do elemento majoritário?
A votação de Boyer-Moore é executada em tempo O(n) e usa O(1) de espaço extra. A contagem com um mapa hash também leva tempo O(n), mas precisa de O(n) de espaço para as contagens. Ordenar primeiro leva tempo O(n log n).
É possível resolver o Problema do Elemento Majoritário usando ordenação?
Sim. Após a ordenação, todas as cópias da maioria ficam em um único bloco com mais da metade do tamanho do array, e qualquer bloco assim contém a posição central. Portanto, o elemento no índice n / 2, arredondado para baixo, é a resposta, com um custo de tempo de O(n log n).
E se o array não tiver um elemento majoritário?
Boyer-Moore sempre retorna algum candidato: em [1, 2, 3], retorna 3. Adicione uma segunda passagem que conte o candidato e aceite-o somente se a contagem for maior que n / 2. O total continua sendo O(n) de tempo e O(1) de espaço.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def majorityElement(nums):
# Escreva o código aquiTeste #1
Teste #2
Argumento
nums = [3, 9, 3, 3, 4]
Saída Esperada
3