347. Top K Frequent Elements

Задача

Дан целочисленный массив nums и целое число k . Верните k наиболее часто встречающихся элементов. Вы можете вернуть ответ в любом порядке.

Решение

Решение

var topKFrequent = function(nums, k) {
    const freq = {};
 
    for (const num of nums) {
        freq[num] = (freq[num] || 0) + 1;
    }
 
    return Object.entries(freq)
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(([int, val]) => parseInt(int, 10));
};

Решение 2

/**
 * Time Complexity: O(N)
 * - O(N) на подсчет частот
 * - O(N) на заполнение buckets
 * - O(N) на сбор результата
 * Итого: O(N)
 * 
 * Space Complexity: O(N)
 * - HashMap с частотами: O(N)
 * - Массив buckets: O(N)
 */
var topKFrequent = function(nums, k) {
    // 1. Подсчитываем частоту каждого элемента
    const freqMap = {};
    for (let num of nums) {
        freqMap[num] = (freqMap[num] || 0) + 1;
    }
 
    // 2. Создаем массив "корзин" (buckets)
    // Индекс массива = частота, значение = список элементов с такой частотой
    // Максимальная частота = nums.length (если все элементы одинаковые)
    const buckets = Array(nums.length + 1).fill(null).map(() => []);
 
    // 3. Распределяем элементы по корзинам
    for (let num in freqMap) {
        const frequency = freqMap[num];
        buckets[frequency].push(Number(num));
    }
 
    // 4. Собираем результат, идя от максимальной частоты к минимальной
    const result = [];
 
    // Идем справа налево (от самых частых к менее частым)
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        if (buckets[i].length > 0) {
            // Добавляем все элементы из текущей корзины
            result.push(...buckets[i]);
        }
    }
 
    // 5. Возвращаем ровно k элементов (на случай если в последней корзине было больше)
    return result.slice(0, k);
};