692. Top K Frequent Words

Задача

Дан массив строк words и целое число k , верните k наиболее часто встречающихся строк.

Верните ответ, отсортированный по частоте от самой высокой к самой низкой. Сортируйте слова с одинаковой частотой в лексикографическом порядке (по алфавиту).

Примеры

Пример 1

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]

Пояснение

“i” и “love” — два самых частых слова; “i” идёт раньше из-за меньшего алфавитного порядка.

Пример 2

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]

Пояснение

“the”, “is”, “sunny”, “day” — четыре самых частых слова с частотами 4, 3, 2, 1.

Решение

Решение

/**
 * Временная сложность: O(N log N)
 * 1. Построение хеша: O(N), где N - количество слов.
 * 2. Сортировка уникальных слов: O(U log U), где U - количество уникальных слов.
 *    В худшем случае U = N, поэтому сложность сортировки O(N log N).
 * 3. map и slice: O(N) и O(k).
 * Итоговая: O(N log N) из-за сортировки.
 *
 * Пространственная сложность: O(N)
 * Храним хеш-таблицу и массив результатов, размер которых пропорционален количеству уникальных слов.
 */
var topKFrequent = function(words, k) {
    const hash = {};
 
    words.forEach((word) => {
        hash[word] = (hash[word] || 0) + 1;
    });
 
    const result = Object.entries(hash).sort((a, b) => {
        const freq = b[1] - a[1];
        // Если частоты равны, сортируем по алфавиту (лексикографически)
        return freq === 0 ? a[0].localeCompare(b[0]) : freq;
    }).map((v) => v[0]);
 
    return result.slice(0, k);
};

Решение 2 (MinHeap)

/**
 * Класс Минимальной Кучи (MinHeap)
 */
class MinHeap {
    constructor(compareFn) {
        this.heap = [];
        this.compare = compareFn;
    }
 
    size() {
        return this.heap.length;
    }
 
    // Добавление элемента
    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }
 
    // Удаление верхушки (минимума)
    pop() {
        if (this.size() === 0) return null;
        const top = this.heap[0];
        const bottom = this.heap.pop();
        if (this.size() > 0) {
            this.heap[0] = bottom;
            this.bubbleDown(0);
        }
        return top;
    }
 
    bubbleUp(idx) {
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            // Если текущий меньше родителя - меняем местами
            if (this.compare(this.heap[idx], this.heap[parentIdx]) < 0) {
                [this.heap[idx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[idx]];
                idx = parentIdx;
            } else {
                break;
            }
        }
    }
 
    bubbleDown(idx) {
        while (true) {
            let swapIdx = null;
            const leftIdx = 2 * idx + 1;
            const rightIdx = 2 * idx + 2;
            const length = this.heap.length;
 
            if (leftIdx < length) {
                if (this.compare(this.heap[leftIdx], this.heap[idx]) < 0) {
                    swapIdx = leftIdx;
                }
            }
 
            if (rightIdx < length) {
                if (
                    (swapIdx === null && this.compare(this.heap[rightIdx], this.heap[idx]) < 0) ||
                    (swapIdx !== null && this.compare(this.heap[rightIdx], this.heap[leftIdx]) < 0)
                ) {
                    swapIdx = rightIdx;
                }
            }
 
            if (swapIdx === null) break;
 
            [this.heap[idx], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[idx]];
            idx = swapIdx;
        }
    }
}
 
/**
 * Временная сложность: O(N log k)
 * Пространственная сложность: O(N)
 */
var topKFrequent = function(words, k) {
    const count = {};
    for (const word of words) {
        count[word] = (count[word] || 0) + 1;
    }
 
    // Функция сравнения для кучи.
    // Возвращает < 0, если a должно быть ВЫШЕ (быть удалено раньше).
    // Мы хотим удалять слова с МЕНЬШЕЙ частотой. 
    // А если частоты равны - удалять слова, которые БОЛЬШЕ по алфавиту (т.к. нам нужны меньшие в топе).
    const compare = (a, b) => {
        if (a.freq !== b.freq) {
            return a.freq - b.freq; // Меньшая частота -> наверх
        }
        return b.word.localeCompare(a.word); // Обратный алфавитный порядок -> наверх
    };
 
    const minHeap = new MinHeap(compare);
 
    for (const [word, freq] of Object.entries(count)) {
        minHeap.push({ word, freq });
        if (minHeap.size() > k) {
            minHeap.pop(); // Выкидываем самый "слабый"
        }
    }
 
    const result = [];
    while (minHeap.size() > 0) {
        result.push(minHeap.pop().word);
    }
 
    // Куча выдала от минимума к максимуму, разворачиваем
    return result.reverse();
};