24 de Março
Os k elementos mais frequentes
Como contar frequência primeiro e depois escolher só os k maiores de forma eficiente.
Frequência e Heap Intermediario 20 min TypeScript
Dado um array de inteiros nums e um inteiro k, retorne os k elementos mais frequentes.
No problema original, qualquer ordem costuma ser aceita. Aqui no SeniorPath, retorne em ordem decrescente de frequência para manter a comparação deterministica.
Exemplo:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
O que perceber antes de codar
- O problema tem duas fases: contar e selecionar.
- Frequência e a informação central. O array original vira materia-prima para construir esse mapa.
- Se você ordenar tudo, resolve. Mas talvez esteja fazendo mais do que precisa.
Erros comuns
- tentar resolver sem contar frequência primeiro
- ordenar o array inteiro em vez de ordenar ou selecionar pelas frequencias
Passo 1 - Separar o problema em duas partes
Muita gente tenta responder direto:
- quem sao os mais frequentes?
Mas antes disso existe uma pergunta menor:
- qual e a frequência de cada valor?
Sem essa etapa, você não tem como comparar nada.
Passo 2 - Escrever a versão inicial mais direta
A versão inicial natural e:
- contar frequência com
mapa hash - transformar em lista de pares
- ordenar pelos maiores
- pegar os
kprimeiros
Funciona bem.
O custo extra esta em ordenar tudo.
Passo 3 - Perguntar o que realmente importa
O problema não pede a lista inteira ordenada.
Ele pede:
- só os K mais frequentes
Isso abre espaco para uma selecao melhor.
Passo 4 - Usar grupos por frequência
A frequência máxima não passa de nums.length.
Entao você pode criar grupos indexados pela frequência onde:
- o indice representa a frequência
- cada grupo guarda os valores com aquela frequência
Depois, basta andar do grupo mais alto para baixo.
Se a frequência não fosse naturalmente limitada, um heap seria um meio-termo comum entre ordenação total e esse agrupamento.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function topKFrequent(nums: number[], k: number): number[] {
// sua solução aqui
return []
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(n)
Solução 1 - Contar com mapa hash e ordenar todos os pares
Boa versão inicial porque deixa as duas fases bem explicitas.
export function topKFrequent(nums: number[], k: number): number[] {
const counts = new Map<number, number>()
for (const num of nums) {
counts.set(num, (counts.get(num) ?? 0) + 1)
}
return [...counts.entries()]
.sort((a, b) => b[1] - a[1] || a[0] - b[0])
.slice(0, k)
.map(([value]) => value)
}Funciona. Mas você ordena todos os candidatos, mesmo querendo só alguns deles.
Solução 2 - Grupos por frequência depois do mapa hash, sem precisar de um heap
Agora a selecao acontece sem ordenação global.
export function topKFrequent(nums: number[], k: number): number[] {
const counts = new Map<number, number>()
for (const num of nums) {
counts.set(num, (counts.get(num) ?? 0) + 1)
}
const buckets = Array.from({ length: nums.length + 1 }, () => [])
for (const [value, frequency] of counts.entries()) {
buckets[frequency].push(value)
}
const result: number[] = []
for (let frequency = buckets.length - 1; frequency >= 0 && result.length < k; frequency -= 1) {
for (const value of buckets[frequency]) {
result.push(value)
if (result.length === k) {
break
}
}
}
return result
}O ponto forte aqui e enxergar que a frequência pode virar indice.
Por isso essa abordagem ganha de um heap aqui: o problema te entrega um intervalo pequeno e limitado de frequencias.
O que dizer na entrevista
Uma explicação curta e boa seria:
Primeiro eu conto a frequência de cada valor com
mapa hash. A versão inicial seria ordenar todos os pares(valor, frequencia)e pegar oskprimeiros. A versão melhor agrupa os valores pela frequência, porque a frequência máxima não passa den. Depois eu caminho do grupo maior para o menor até completarkelementos emO(n).
Isso mostra que você:
- separou bem contagem e selecao
- justificou por que a ordenação total não era obrigatoria
- explicou a estrutura da solução sem misterio
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- contar frequência antes de decidir
- selecionar os
kmaiores - discutir quando vale usar ordenação total, um
heapou grupos por frequência - transformar um atributo limitado em indice
O ponto não e decorar esse problema.
O ponto e aprender a separar “medir” de “escolher”.