LeetCode 347. Os K Elementos Mais Frequentes (Dificuldade Média)

Dado um array de inteiros nums e um valor inteiro k, retorne os k elementos com as frequências mais altas. A ordem dos resultados pode ser arbitrária.

Abordagem Central

O problema exige duas etapas principais: contagem de frequência e seleção dos k maiores. O uso de estruturas de heap permite otimizar essa operação. #### Método 1: Heap Mínimo (Recomendado, Complexidade O(n log k))

• Contagem: Utilize um Map<Integer, Integer> para registrar quantas vezes cada número aparece.
• Filtragem via Heap: Mantenha um heap mínimo com tamanho máximo igual a k. Para cada par elemento-frequência, se o heap ainda não estiver cheio, adicione-o. Caso contrário, apenas inclua se a nova frequência for maior que a do topo do heap (menor frequência atual).
• Coleta Final: Após processar todos os elementos, o heap conterá os k elementos com maior frequência.

Método 2: Heap Máximo (Simples, mas menos eficiente)

Armazene todos os elementos no heap máximo baseado na frequência e extraia os primeiros k. Porém, isso resulta em complexidade O(n log n), inferior ao método anterior. ### Código (Java – Heap Mínimo)

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> frequency = new HashMap<>();
    for (int num : nums) {
        frequency.put(num, frequency.getOrDefault(num, 0) + 1);
    }

    PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
        Comparator.comparingInt(Map.Entry::getValue)
    );

    for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
        if (minHeap.size() < k) {
            minHeap.offer(entry);
        } else if (entry.getValue() > minHeap.peek().getValue()) {
            minHeap.poll();
            minHeap.offer(entry);
        }
    }

    int[] result = new int[k];
    int index = 0;
    while (!minHeap.isEmpty()) {
        result[index++] = minHeap.poll().getKey();
    }
    return result;
}

Pontos-Chave da Revisão

• O heap mínimo é preferível porque limita o tamanho a k, reduzindo o custo das operações para O(log k).
• Evite confundir a ordem de comparação: o heap deve ordenar por frequência crescente, não pelo valor do elemento.

LeetCode 295. Mediana em Fluxo de Dados (Dificuldade Alta)

Implemente uma estrutura capaz de adicionar números em tempo real e retornar a mediana do conjunto atual. As operações são:

• addNum(int num): adiciona um número ao fluxo.
• findMedian(): retorna a mediana dos números inseridos até agora.

Abordagem Central: Dual Heap (Pares de Pilhas)

Utilize dois heaps para dividir os dados em partes: - Heap Máximo (esquerda): armazena os menores elementos; seu topo é o maior dentre eles.

• Heap Mínimo (direita): armazena os maiores elementos; seu topo é o menor dentre eles.

Regras de Balanceamento

• O heap esquerdo pode ter no máximo um elemento a mais que o direito. - Após cada inserção, ajuste os heaps para manter essa propriedade. ### Código (Java)

class MedianFinder {
    private PriorityQueue<Integer> left;   // Max heap
    private PriorityQueue<Integer> right;  // Min heap

    public MedianFinder() {
        left = new PriorityQueue<>((a, b) -> b - a); // max
        right = new PriorityQueue<>();              // min
    }

    public void addNum(int num) {
        if (left.isEmpty() || num <= left.peek()) {
            left.offer(num);
        } else {
            right.offer(num);
        }

        // Corrigir desequilíbrio
        if (left.size() > right.size() + 1) {
            right.offer(left.poll());
        } else if (right.size() > left.size()) {
            left.offer(right.poll());
        }
    }

    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        } else {
            return (left.peek() + right.peek()) / 2.0;
        }
    }
}

Pontos-Chave da Revisão

• Os dois heaps permitem obter a mediana em O(1), pois os valores centrais estão nos topos.
• Verifique cuidadosamente as condições de balanceamento: erro na lógica leva a resultados incorretos.
• Alternativas como lista ordenada com busca binária têm custo O(n) para inserção — inferior à solução com heaps.

Resumo dos Modelos Essenciais