Top K частых элементов: разбор задачи

Почему эта задача важна?

Задача на поиск k наиболее частых элементов позволяет оценить:

• Умение работать с хеш-таблицами и кучами
• Навыки эффективной сортировки данных
• Способность оптимизировать алгоритмы по времени и памяти
• Понимание структур данных для подсчета частот

Постановка задачи

Формулировка:

Дан массив целых чисел nums и число k. Нужно найти k элементов, которые встречаются чаще всего.

Примеры:

// Первый пример
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]  // 1 встречается 3 раза, 2 встречается 2 раза

// Второй пример
Input: nums = [1], k = 1
Output: [1]

// Третий пример
Input: nums = [1,2,2,3,3,3], k = 2
Output: [3,2]  // 3 встречается 3 раза, 2 встречается 2 раза

Подходы к решению

Решение 1: Сортировка по частоте (базовый подход)

function topKFrequent(nums, k) {
    const frequency = new Map();
    
    // Подсчет частоты каждого элемента
    for (const num of nums) {
        frequency.set(num, (frequency.get(num) || 0) + 1);
    }
    
    // Преобразование в массив и сортировка по частоте
    return Array.from(frequency.entries())
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(entry => entry[0]);
}

Анализ решения:

✅ Простая реализация

✅ Понятная логика работы

❌ Временная сложность O(n log n)

❌ Избыточная сортировка всех элементов

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Решение 2: Использование кучи (Heap)

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    push(value) {
        this.heap.push(value);
        this.heapifyUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const result = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown();
        return result;
    }
    
    // ... остальные методы кучи
}

function topKFrequent(nums, k) {
    const frequency = new Map();
    for (const num of nums) {
        frequency.set(num, (frequency.get(num) || 0) + 1);
    }
    
    const minHeap = new MinHeap();
    for (const [num, freq] of frequency.entries()) {
        minHeap.push([freq, num]);
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    return minHeap.heap.map(item => item[1]);
}

Характеристики:

✅ Оптимальная временная сложность O(n log k)

✅ Эффективное использование памяти

❌ Сложная реализация кучи

❌ Требует дополнительной структуры данных

Решение 3: Быстрый выбор (Quick Select)

function topKFrequent(nums, k) {
    // Подсчет частоты
    const frequency = new Map();
    for (const num of nums) {
        frequency.set(num, (frequency.get(num) || 0) + 1);
    }
    
    const unique = Array.from(frequency.keys());
    
    // Функция разделения для быстрого выбора
    function partition(left, right, pivotIndex) {
        const pivotFreq = frequency.get(unique[pivotIndex]);
        [unique[pivotIndex], unique[right]] = [unique[right], unique[pivotIndex]];
        let storeIndex = left;
        
        for (let i = left; i < right; i++) {
            if (frequency.get(unique[i]) > pivotFreq) {
                [unique[storeIndex], unique[i]] = [unique[i], unique[storeIndex]];
                storeIndex++;
            }
        }
        
        [unique[right], unique[storeIndex]] = [unique[storeIndex], unique[right]];
        return storeIndex;
    }
    
    // Быстрый выбор
    function quickSelect(left, right, kSmallest) {
        if (left === right) return;
        
        const pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
        const pivot = partition(left, right, pivotIndex);
        
        if (pivot === kSmallest) return;
        else if (kSmallest < pivot) quickSelect(left, pivot - 1, kSmallest);
        else quickSelect(pivot + 1, right, kSmallest);
    }
    
    quickSelect(0, unique.length - 1, k);
    return unique.slice(0, k);
}

Преимущества и недостатки:

✅ Оптимальная средняя сложность O(n)

✅ Не требует дополнительных структур данных

❌ Сложная реализация

❌ Худший случай O(n²)

Рекомендации по решению

1. Выбор метода решения:

   • Сортировка - для простых случаев и малых данных
   • Куча - для больших данных с ограниченным k
   • Быстрый выбор - для больших данных с большим k

2. Важные моменты:

   • Эффективный подсчет частот
   • Правильная обработка одинаковых частот
   • Оптимизация по памяти

Распространённые ошибки

1. Неправильная обработка элементов с одинаковой частотой
2. Избыточное использование памяти при подсчете
3. Неоптимальный выбор структур данных

Оптимизации

Оптимизация подсчета частот

function topKFrequent(nums, k) {
    if (nums.length === k) return nums;
    
    // Используем массив для подсчета, если диапазон чисел известен
    const frequency = new Map();
    const buckets = Array(nums.length + 1).fill().map(() => []);
    
    // Подсчет частот
    for (const num of nums) {
        frequency.set(num, (frequency.get(num) || 0) + 1);
    }
    
    // Распределение по корзинам
    for (const [num, freq] of frequency) {
        buckets[freq].push(num);
    }
    
    // Сбор результата
    const result = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
        result.push(...buckets[i]);
    }
    
    return result.slice(0, k);
}

Заключение

При решении задачи важно учитывать:

• Компромисс между временем выполнения и использованием памяти
• Особенности входных данных
• Требования к порядку элементов в результате

Эта задача демонстрирует важность выбора правильной структуры данных и алгоритма в зависимости от характеристик входных данных.