Топ K частых элементов

Топ K частых элементов

Описание задачи

Нужно найти K элементов с наивысшей частотой в массиве. Требуется решение лучше O(n log n) (лучше, чем сортировка).

Это позволяет использовать специализированные структуры данных: heap или bucket sort.

Подход 1: Min Heap (оптимальный)

Держим в heap только K элементов с наивысшей частотой:

import heapq
from collections import Counter

def topKFrequent(nums: list[int], k: int) -> list[int]:
    # Шаг 1: Подсчитываем частоту каждого элемента
    count = Counter(nums)
    
    # Шаг 2: Используем min heap размером k
    # heap хранит (частота, элемент)
    heap = []
    
    for num, freq in count.items():
        if len(heap) < k:
            # Если heap не полный, добавляем
            heapq.heappush(heap, (freq, num))
        elif freq > heap[0][0]:
            # Если частота больше, чем минимальная в heap
            heapq.heapreplace(heap, (freq, num))
    
    # Шаг 3: Извлекаем элементы из heap
    return [num for freq, num in heap]

# Примеры
print(topKFrequent([1, 1, 1, 2, 2, 3], 2))        # [1, 2]
print(topKFrequent([1], 1))                        # [1]
print(topKFrequent([4, 1, 1, 1, 2, 2, 3], 2))     # [1, 2]
print(topKFrequent([5, 5, 5, 5, 1, 1], 1))        # [5]

Логика:

1. Подсчитываем частоту каждого элемента с помощью Counter
2. Используем min heap размером K:
   • Min heap содержит K элементов с наивысшей частотой
   • Вершина heap — элемент с минимальной частотой из K
3. Для каждого элемента:
   • Если heap не полный (< K): добавляем элемент
   • Если heap полный и частота больше минимальной: заменяем минимальный
4. В конце heap содержит K элементов с наивысшей частотой

Сложность:

• Временная: O(n log k) — добавление/удаление в heap O(log k), делаем n раз
• Пространственная: O(n) для Counter + O(k) для heap

Подход 2: Bucket Sort (лучший)

Ещё более эффективный подход — группируем по частоте:

from collections import Counter

def topKFrequent_v2(nums: list[int], k: int) -> list[int]:
    # Шаг 1: Подсчитываем частоту
    count = Counter(nums)
    
    # Шаг 2: Создаём "buckets" — массив массивов
    # buckets[i] содержит все элементы с частотой i
    buckets = [[] for _ in range(len(nums) + 1)]
    
    for num, freq in count.items():
        buckets[freq].append(num)
    
    # Шаг 3: Идём с конца и собираем K элементов
    result = []
    for i in range(len(buckets) - 1, 0, -1):
        for num in buckets[i]:
            result.append(num)
            if len(result) == k:
                return result
    
    return result

print(topKFrequent_v2([1, 1, 1, 2, 2, 3], 2))     # [1, 2]
print(topKFrequent_v2([1], 1))                     # [1]
print(topKFrequent_v2([4, 1, 1, 1, 2, 2, 3], 2))  # [1, 2]

Логика:

1. Подсчитываем частоту каждого элемента
2. Создаём массив "buckets", где buckets[i] — список элементов с частотой i
3. Проходим по buckets с конца (от максимальной частоты):
   • Собираем элементы пока не наберём K
4. Возвращаем результат

Пример:

нумс = [1, 1, 1, 2, 2, 3]
count = {1: 3, 2: 2, 3: 1}

buckets = [
  [],        # частота 0
  [3],       # частота 1
  [2],       # частота 2
  [1],       # частота 3
]

Идём с конца:
  buckets[3] = [1] → result = [1]
  buckets[2] = [2] → result = [1, 2] (k=2, стоп)

Сложность:

• Временная: O(n) — линейная!
• Пространственная: O(n) для buckets и Counter

Подход 3: Max Heap (простой способ)

Менее оптимально, но проще:

import heapq
from collections import Counter

def topKFrequent_v3(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    
    # Используем negative frequencies для max heap
    heap = [(-freq, num) for num, freq in count.items()]
    heapq.heapify(heap)  # O(n)
    
    # Извлекаем K элементов
    result = []
    for _ in range(k):
        freq, num = heapq.heappop(heap)
        result.append(num)
    
    return result

print(topKFrequent_v3([1, 1, 1, 2, 2, 3], 2))     # [1, 2]

Сложность: O(n + k log n) — чуть хуже, чем min heap

Подход 4: Сортировка (простой способ)

Для интервью, если забыли про heap/bucket sort:

from collections import Counter

def topKFrequent_v4(nums: list[int], k: int) -> list[int]:
    count = Counter(nums)
    
    # Сортируем по частоте (descending)
    sorted_items = sorted(count.items(), key=lambda x: x[1], reverse=True)
    
    # Берём первые k элементов
    return [num for num, freq in sorted_items[:k]]

print(topKFrequent_v4([1, 1, 1, 2, 2, 3], 2))     # [1, 2]

Сложность: O(n log n) — не подходит к требованиям, но работает

Тестирование

import unittest

class TestTopKFrequent(unittest.TestCase):
    def setUp(self):
        self.solution = topKFrequent
    
    def test_basic(self):
        result = self.solution([1, 1, 1, 2, 2, 3], 2)
        self.assertEqual(sorted(result), [1, 2])
    
    def test_single_element(self):
        self.assertEqual(self.solution([1], 1), [1])
    
    def test_k_equals_length(self):
        result = self.solution([1, 2, 3], 3)
        self.assertEqual(sorted(result), [1, 2, 3])
    
    def test_duplicate_frequencies(self):
        # Все элементы с одинаковой частотой
        result = self.solution([1, 1, 2, 2, 3, 3], 2)
        self.assertEqual(len(result), 2)
    
    def test_large_k(self):
        result = self.solution([1, 1, 1, 2, 2, 3], 3)
        self.assertEqual(len(result), 3)
        self.assertIn(1, result)
        self.assertIn(2, result)
        self.assertIn(3, result)
    
    def test_negative_numbers(self):
        result = self.solution([-1, -1, -2, 2], 2)
        self.assertEqual(len(result), 2)
    
    def test_large_array(self):
        # Большой массив
        nums = [1] * 1000 + [2] * 500 + [3] * 100
        result = self.solution(nums, 2)
        self.assertEqual(sorted(result), [1, 2])

Визуализация (Min Heap)

нумс = [1, 1, 1, 2, 2, 3], k=2
count = {1: 3, 2: 2, 3: 1}

Шаг 1: Добавляем (3, 1)
  heap = [(3, 1)]

Шаг 2: Добавляем (2, 2)
  heap = [(2, 2), (3, 1)]

Шаг 3: (1, 3) < (2, 2)? Нет, не добавляем

Результат: heap = [(2, 2), (3, 1)]
Элементы: [1, 2]

Сравнение подходов

Ключевые моменты

1. Min Heap размером k держит только нужные элементы
2. heapreplace эффективнее, чем pop + push
3. Bucket Sort линейный! Используем индекс частоты
4. Counter из collections — лучший способ подсчёта

Заключение

Для интервью рекомендуется:

1. Bucket Sort — если вы знаете эту технику (O(n))
2. Min Heap — если забыли про bucket sort (O(n log k))
3. Сортировка — если совсем забыли всё (O(n log n), не подходит)

Это демонстрирует, как правильный выбор структуры данных даёт экспоненциальное улучшение производительности!