0Pricing
DSA Interview Prep · Урок

Подсчёт частот и группировка

Используйте Counter и defaultdict для подсчёта частот символов, группируйте анаграммы по отсортированному ключу и находите k наиболее частых элементов

«Подсчёт частот и группировка» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.

Подсчёт частот: основной шаблон

Подсчёт частот — один из самых универсальных шаблонов на собеседованиях по программированию. Подсчитывая, сколько раз каждый элемент встречается в списке или строке, можно отвечать на вопросы о дубликатах, анаграммах, наиболее частых элементах и допустимых расположениях за O(n) времени — значительно лучше, чем при альтернативном подходе с сортировкой и последовательным просмотром за O(n log n).

Стандартными инструментами служат Counter и defaultdict(int). Оба создают отображение элемента в его количество; Counter дополнительно поддерживает арифметические операции и most_common.

from collections import Counter

words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq  = Counter(words)
print(freq)                  # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple'])         # 3
print(freq['grape'])         # 0 (not KeyError)
print(freq.most_common(2))   # [('apple',3),('banana',2)]

Проверка анаграммы (LeetCode 242)

LeetCode 242 «Проверка анаграммы»: определите, являются ли две строки анаграммами друг друга. Две строки являются анаграммами, если частоты их символов совпадают. Сравните объекты счётчика или отсортируйте обе строки. Использование счётчика занимает O(n), а сортировка — O(n log n). Подход со счётчиком оптимален и непосредственно отражает определение.

from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)

# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
    if len(s) != len(t):
        return False
    freq = [0] * 26
    for c in s: freq[ord(c) - ord('a')] += 1
    for c in t: freq[ord(c) - ord('a')] -= 1
    return all(f == 0 for f in freq)

print(isAnagram('anagram', 'nagaram'))  # True
print(isAnagram('rat', 'car'))          # False
print(isAnagram_arr('listen', 'silent'))  # True

Группировка анаграмм (LeetCode 49)

LeetCode 49 «Группировка анаграмм»: получив список строк, сгруппируйте все анаграммы вместе. Главная идея: у анаграмм одна и та же отсортированная последовательность символов. Используйте defaultdict(list) с ключом, заданным отсортированным кортежем символов строки (кортежи допускают хеширование). Каждая группа накапливается под одним и тем же ключом. Время выполнения: O(n × L log L), где L — максимальная длина строки.

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))   # hashable canonical form
        groups[key].append(s)
    return list(groups.values())

print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]

# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(ord(c) - ord('a') for c in sorted(s))
        groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
    return list(groups.values())

K наиболее частых элементов (LeetCode 347)

LeetCode 347 «K наиболее частых элементов»: верните k элементов, встречающихся чаще всего. Прямой подход занимает O(n log n): подсчитать частоты, отсортировать по убыванию частоты и взять первые k элементов. Оптимальный подход за O(n) использует сортировку по корзинам: создайте корзины с индексами, соответствующими частотам (от 1 до n), поместите каждый элемент в корзину его частоты, а затем просматривайте корзины от самой высокой частоты к самой низкой, собирая k элементов.

from collections import Counter

def topKFrequent(nums, k):
    freq  = Counter(nums)
    # Bucket sort by frequency
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, count in freq.items():
        buckets[count].append(num)
    result = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
    return result

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

Сортировка символов по частоте (LeetCode 451)

LeetCode 451 «Сортировка символов по частоте»: перестройте строку так, чтобы символы располагались в порядке убывания частоты. Подсчитайте частоты, отсортируйте символы по убыванию частоты и объедините их. Использование most_common — самый понятный подход в Python. Время выполнения: O(n log n) для сортировки уникальных символов по частоте.

from collections import Counter

def frequencySort(s):
    freq = Counter(s)
    return ''.join(ch * count for ch, count in freq.most_common())

print(frequencySort('tree'))    # 'eetr' or 'eert'
print(frequencySort('cccaaa'))  # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb'))    # 'bbAa' or 'bbaA'

Планировщик задач (LeetCode 621)

LeetCode 621 «Планировщик задач»: получив задачи и интервал ожидания n, найдите минимальное время для выполнения всех задач. Ключевая идея: структура расписания определяется задачей с наибольшей частотой. Разместите max_count копий самой частой задачи с промежутками длиной n. Минимальное общее время = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Если разных задач достаточно, чтобы заполнить промежутки, время простоя равно 0.

from collections import Counter

def leastInterval(tasks, n):
    freq      = Counter(tasks)
    max_count = max(freq.values())
    # How many tasks share the max frequency
    num_max   = sum(1 for v in freq.values() if v == max_count)
    # Minimum slots needed based on most frequent task
    min_slots = (max_count - 1) * (n + 1) + num_max
    return max(min_slots, len(tasks))

print(leastInterval(['A','A','A','B','B','B'], 2))  # 8
print(leastInterval(['A','A','A','B','B','B'], 0))  # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2))  # 10

Поиск большинства с помощью счётчика

LeetCode 169 «Элемент, составляющий большинство»: найдите элемент, встречающийся более n/2 раз. Хотя голосование Бойера — Мура является оптимальным решением с O(1) дополнительной памяти, использование Counter.most_common(1) решает задачу напрямую за O(n) времени и O(n) дополнительной памяти. Если на собеседовании требуется решение с O(1) дополнительной памяти, предложите алгоритм Бойера — Мура как следующий вариант; если дополнительная память разрешена, счётчик выглядит проще.

from collections import Counter

def majorityElement_counter(nums):
    freq = Counter(nums)
    return freq.most_common(1)[0][0]

# Boyer-Moore O(1) space
def majorityElement_moore(nums):
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums))  # 2
print(majorityElement_moore(nums))    # 2

Первый неповторяющийся символ

LeetCode 387 «Первый уникальный символ в строке»: найдите индекс первого символа, встречающегося ровно один раз. Подход в два прохода: на первом проходе создайте таблицу частот, а на втором найдите первый символ с частотой 1. Время выполнения: O(n), память: O(1), поскольку алфавит фиксирован и содержит 26 символов.

from collections import Counter

def firstUniqChar(s):
    freq = Counter(s)
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

print(firstUniqChar('leetcode'))   # 0 (l)
print(firstUniqChar('loveleetcode'))  # 2 (v)
print(firstUniqChar('aabb'))       # -1

Сумма подмассива равна K (LeetCode 560)

LeetCode 560 «Сумма подмассива равна K»: подсчитайте подмассивы с суммой k. Перебор всех вариантов занимает O(n²). Подход за O(n): поддерживайте текущую префиксную сумму и таблицу частот уже встречавшихся префиксных сумм. Для каждой позиции i количество подмассивов, заканчивающихся в i и имеющих сумму k, равно количеству более ранних префиксных сумм, равных (current_prefix_sum - k). Инициализируйте таблицу значением {0: 1}, чтобы учитывать подмассивы, начинающиеся с индекса 0.

from collections import defaultdict

def subarraySum(nums, k):
    freq         = defaultdict(int)
    freq[0]      = 1   # prefix sum of 0 seen once (empty prefix)
    prefix_sum   = 0
    count        = 0
    for num in nums:
        prefix_sum += num
        # How many earlier prefix sums allow a k-sum subarray ending here
        count      += freq[prefix_sum - k]
        freq[prefix_sum] += 1
    return count

print(subarraySum([1, 1, 1], 2))            # 2
print(subarraySum([1, 2, 3], 3))            # 2
print(subarraySum([1, -1, 1, -1, 1], 0))   # 4

Арифметика счётчиков и пересечение

Counter поддерживает арифметические операции: + объединяет счётчики (складывает количества), - вычитает (ограничивает результат нулём), & берёт минимум (пересечение), а | берёт максимум (объединение). Эти операции упрощают такие задачи, как «найти общие символы в нескольких строках» или «удалить минимальное количество символов, чтобы одна строка стала анаграммой другой».

from collections import Counter

A = Counter('abccdd')
B = Counter('ccdde')

print('Add:      ', dict(A + B))  # sum of counts
print('Subtract: ', dict(A - B))  # A - B, clipped at 0
print('Intersect:', dict(A & B))  # min of shared counts
print('Union:    ', dict(A | B))  # max counts

# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values()))  # 5

Итоги: когда использовать подсчёт частот

Выбирайте подсчёт частот, когда задача включает: проверку эквивалентности двух строк с точностью до перестановки символов (анаграмма), поиск наиболее или наименее частых элементов, проверку того, что набор содержит нужный «состав», или преобразование задачи о подмассиве или подстроке в задачу о префиксной сумме с таблицей. Главное, что порядок элементов внутри группы не имеет значения — важны только количества.

Для ясности всегда используйте Counter; переходите на обычный dict или массив только при необходимости более точного управления либо строгого требования O(1) дополнительной памяти при ограниченном алфавите.

Быстрая проверка

Проверьте, насколько хорошо вы поняли концепции «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.

Итоги урока

В этом уроке вы узнали: Counter обеспечивает подсчёт частот за O(n), поддерживает most_common, арифметические операторы и доступ с нулевым значением по умолчанию, группировка по канонической форме (отсортированному кортежу) решает задачу группировки анаграмм за O(nL log L), а префиксная сумма с таблицей частот преобразует задачу о подмассивах с суммой k из O(n²) в O(n). Далее мы разберём задачу о самой длинной последовательности последовательных чисел и проектирование кэша LRU.

Часто задаваемые вопросы

Урок «Подсчёт частот и группировка» бесплатный?

Да — полный текст урока «Подсчёт частот и группировка» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Подсчёт частот и группировка»?

Используйте Counter и defaultdict для подсчёта частот символов, группируйте анаграммы по отсортированному ключу и находите k наиболее частых элементов Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать DSA Interview Prep?

Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Подсчёт частот и группировка»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке DSA Interview Prep?

Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Внутреннее устройство хеш-функций и обработка коллизий
  2. Два слагаемых и множество вариантов
  3. Подсчёт частот и группировка
  4. Самая длинная последовательность и кэш LRU
← Назад к DSA Interview Prep