Top K Frequent Elements
Você recebe um array de números inteiros nums e um número inteiro k. Retorne os k valores que aparecem com mais frequência em nums, começando pelo mais frequente. Quando dois valores aparecem o mesmo número de vezes, o menor vem primeiro.
Cada valor aparece uma vez na resposta, independentemente de quantas vezes apareça em nums, e k nunca é maior que o número de valores distintos.
Função
- numsinteger-array
- os valores a contar
- kinteger
- quantos valores retornar
- Retornainteger-array
- os k valores mais frequentes, em ordem decrescente de frequência; em caso de empate, primeiro o menor valor
Restrições
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, eké no máximo o número de valores distintos emnums.
Exemplos
- Entrada
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Saída
- [4, 1]
- Explicação
4ocorre quatro vezes,1três vezes, e2e3uma vez cada. Os dois valores mais frequentes são4, seguido de1.
- Entrada
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Saída
- [-2, 5]
- Explicação
-2,5e7aparecem duas vezes cada, e9uma vez. Três valores empatam no primeiro lugar, então os dois menores,-2e5, são a resposta.
- Entrada
- nums = [8]k = 1
- Saída
- [8]
- Explicação
- Há um único valor, então ele é o mais frequente.
+16 testes ocultos ao enviar
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Comece descobrindo com que frequência cada valor ocorre. Qual estrutura de dados associa um valor à sua contagem em uma única passagem?
Com as contagens em mãos, você quer os
kmelhores valores segundo uma ordenação: primeiro, a maior contagem; em caso de empate, o menor valor. Ordenar todos os valores distintos funciona. Um heap mínimo de tamanhokmantém apenas os valores que ainda podem fazer parte da resposta.Uma contagem é um número inteiro de 1 a
n. Crie um balde para cada contagem; o baldeccontém os valores que ocorrem exatamentecvezes, e percorra os baldes da maior contagem para a menor. Preencha os baldes percorrendo os valores do menor para o maior, e cada balde já estará na ordem de desempate.
Solução
A contagem é a parte rápida: uma única passagem com um mapa de hash fornece a contagem de cada valor. A verdadeira questão é como escolher os k melhores valores sem fazer mais trabalho do que o necessário. Ordenar todos os d valores distintos pela contagem custa O(d log d); um heap mínimo de tamanho k reduz esse custo para O(d log k); e, como uma contagem é um número inteiro de 1 a n, uma ordenação por baldes ordena os valores pela contagem sem fazer nenhuma comparação.
Conte e, em seguida, ordene pela contagem
Intuição
Conte primeiro. Uma passagem com um mapa hash de valor para contagem transforma [4, 1, 4, 2, 1, 4, 3, 1, 4] em 4 → 4, 1 → 3, 2 → 1, 3 → 1.
Depois, coloque os valores distintos na ordem da resposta: primeiro a maior contagem e, em caso de empate, primeiro o menor valor. Faça a ordenação usando exatamente essa comparação, com a contagem como primeira chave e o valor como segunda, e as primeiras k entradas da lista ordenada serão a resposta. Aqui, a ordem é 4, 1, 2, 3, e k = 2 mantém 4 e 1.
A contagem custa O(n). Ordenar os d valores distintos custa O(d log d), no máximo O(n log n) quando todos os valores são diferentes: 10^4 valores exigem cerca de 1.3 × 10^5 comparações, o que é rápido. O desperdício é que a ordenação organiza todos os valores quando apenas os primeiros k importam.
Algoritmo
- Conte cada valor em um mapa hash.
- Coloque os valores distintos em uma lista.
- Ordene a lista pela contagem, da maior para a menor, e pelo valor, do menor para o maior, quando as contagens forem iguais.
- Retorne os primeiros
kvalores.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]Mantenha os k melhores em um min-heap
Intuição
Você precisa apenas dos k melhores valores, então mantenha apenas k candidatos. Para cada novo valor, a questão é se ele supera o candidato mais fraco que você mantém, em que mais fraco significa uma contagem menor ou a mesma contagem e um valor maior. Um min-heap ordenado por essa regra mantém o candidato mais fraco no topo, onde você o consulta em O(1) e o substitui em O(log k).
Percorra os valores distintos. Enquanto o heap tiver menos de k elementos, adicione o valor. Depois disso, um valor que supera o elemento do topo o substitui, e um valor que não supera é descartado, porque k valores melhores já estão sendo mantidos. Com um heap de biblioteca, é mais curto inserir todos os valores e remover um elemento sempre que o heap ultrapassar k, o que mantém os mesmos k valores.
No final, o heap contém a resposta, mas não na ordem da resposta: um heap é apenas parcialmente ordenado. Remover elementos retorna primeiro o valor mais fraco, então escreva a resposta da última posição para a primeira.
Cada um dos d valores distintos custa no máximo uma operação de heap em k elementos, então a seleção leva O(d log k). Isso é mais rápido do que ordenar quando k é muito menor que d, como ao selecionar os 10 maiores entre 8000 valores distintos.
Algoritmo
- Conte cada valor em um mapa hash.
- Para cada valor distinto, insira-o enquanto o heap contiver menos de
kvalores. - Quando o heap estiver cheio, compare o valor com o topo, o valor mais fraco mantido. Se o novo valor for mais forte, coloque-o no topo e faça-o descer no heap.
- Remova o elemento do heap
kvezes, escrevendo cada valor na resposta da última posição para a primeira.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultConte e, em seguida, ordene em buckets pela contagem
Intuição
Uma contagem não é qualquer número: é um número inteiro de 1 a n. Isso permite usar uma ordenação por baldes. Crie um balde para cada contagem, com o balde c contendo os valores que ocorrem exatamente c vezes, e percorra os baldes do n até 1. Os valores saem do mais frequente para o menos frequente, e nenhuma contagem é comparada com outra.
A regra de desempate exige mais uma coisa: dentro de um balde, o menor valor deve vir primeiro. Os valores estão entre -10^4 e 10^4, então um array de R = 2 × 10^4 + 1 contadores pode fazer a contagem, com o valor v no índice v + 10^4. Percorra esse array do menor valor ao maior e acrescente cada valor ao balde correspondente à sua contagem. Cada balde é preenchido em ordem crescente, que é a ordem de desempate, então não é necessário ordenar nada.
Para [5, -2, 7, -2, 7, 5, 9], o percurso coloca -2, 5, 7 no balde 2, nessa ordem, e 9 no balde 1. Ao percorrer os baldes a partir do 7, o primeiro balde com valores é o balde 2, e k = 2 seleciona -2 e 5.
O trabalho consiste em uma passagem por nums, uma passagem pelos R contadores e uma passagem pelos baldes, O(n + R) no total: linear para um intervalo fixo de valores. Com um mapa hash no lugar do array de contagem, a contagem continua linear, mas os baldes são preenchidos na ordem do mapa, e seria necessário ordenar cada um para respeitar a regra de desempate.
Algoritmo
- Conte cada valor em um array indexado por
value + 10^4. - Crie os buckets de 1 a
n, uma lista para cada contagem possível. - Percorra o array de contagem do menor valor ao maior e adicione cada valor que ocorre ao bucket correspondente à sua contagem.
- Leia os buckets da contagem
naté 1, selecionando valores até obterk.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
Armadilhas e casos extremos
A contagem raramente está errada. A ordem da resposta é que costuma estar.
- Desempatar pela ordem da primeira ocorrência ou pela ordem do mapa hash. No segundo exemplo,
-2,5e7aparecem duas vezes cada, e só a regra do menor valor faz de[-2, 5]a única resposta correta. - Retornar o array do heap tal como está. Um heap é apenas parcialmente ordenado, e seu topo é o valor mais fraco, aquele que deve ficar por último.
- Inverter a regra de desempate do heap. Entre dois valores com a mesma contagem, o maior é mais fraco, então um min-heap em
(count, value)remove o valor errado. Use(count, -value)ou uma comparação escrita para seguir a regra. - Criar apenas a quantidade de buckets correspondente ao número de valores distintos. Um valor pode ocorrer
nvezes, como em[3, 3, 3, 3], então o bucketnprecisa existir. - Em Java, comparar duas contagens
Integercom!=. Isso compara as referências e falha quando as contagens passam de 127. Primeiro, converta-as paraint. - Pegar um bucket inteiro no final. Pare assim que tiver
kvalores, mesmo que esteja no meio de um bucket.
Perguntas frequentes4
Qual é a complexidade de tempo para encontrar os K elementos mais frequentes?
A contagem leva O(n). Selecionar os k maiores valores custa então O(d log d) com uma ordenação dos d valores distintos, O(d log k) com um min-heap de tamanho k e O(n) mais uma passagem pelo intervalo de valores com ordenação por buckets. Como d pode chegar a n, a ordenação custa O(n log n) no pior caso, e a ordenação por buckets é linear.
É possível resolver Top K Frequent Elements em tempo O(n)?
Sim, com ordenação por baldes. As contagens são números inteiros de 1 a n, então cada valor vai para o balde correspondente à sua contagem, e ler os baldes da maior contagem para a menor lista os valores por frequência sem nenhuma ordenação por comparação. A seleção rápida nas contagens também é O(n) em média, mas, no pior caso, é quadrática.
Por que usar um heap mínimo e não um heap máximo?
Um max-heap com todos os d valores também funciona: monte-o em O(d) e remova um elemento k vezes, O(d + k log d) no total. Um min-heap de tamanho k mantém apenas k entradas e é adequado para valores que chegam um de cada vez, pois o topo é o candidato a ser removido. O custo é que ele libera a resposta na ordem inversa, então você preenche o resultado de trás para frente.
Como você desempata em Top K Frequent Elements?
Escolha uma regra e aplique-a em todos os casos; aqui, contagens iguais colocam o menor valor primeiro, o que torna a resposta única. Em uma ordenação, compare as contagens e, em seguida, os valores. Em um heap, entre duas contagens iguais, o maior valor é o menos prioritário. Em uma ordenação por balde, preencha os baldes em ordem crescente de valor, e cada balde já estará na ordem de desempate.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def topKFrequent(nums, k):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Esperado
[4, 1]