Zliczanie częstotliwości i grupowanie
Wykorzystają Państwo Counter i defaultdict do zliczania częstotliwości znaków, grupowania anagramów według posortowanego klucza oraz znajdowania elementów o największej częstotliwości top-k.
Zliczanie częstotliwości i grupowanie to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Zliczanie częstotliwości: podstawowy schemat
Zliczanie częstotliwości należy do najbardziej wszechstronnych schematów stosowanych podczas rozmów rekrutacyjnych dotyczących programowania. Zliczając, jak często każdy element występuje na liście lub w napisie, można odpowiadać na pytania dotyczące duplikatów, anagramów, najczęściej występujących elementów i poprawnych układów w czasie O(n) — znacznie lepiej niż w alternatywnym podejściu O(n log n) polegającym na sortowaniu i skanowaniu.
Standardowymi narzędziami w Pythonie są Counter i defaultdict(int). Oba tworzą mapowanie elementu na jego liczność, a Counter dodatkowo obsługuje działania arytmetyczne i metodę 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)]Poprawny anagram (LeetCode 242)
LeetCode 242 „Poprawny anagram”: należy ustalić, czy dwa napisy są wzajemnie anagramami. Dwa napisy są anagramami, jeśli mają takie same częstości znaków. Należy porównać ich obiekty Counter albo posortować oba napisy. Użycie Counter ma złożoność O(n), a sortowanie — O(n log n). Podejście z Counter jest optymalne i bezpośrednio odzwierciedla definicję.
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')) # TrueGrupowanie anagramów (LeetCode 49)
LeetCode 49 „Grupowanie anagramów”: mając listę napisów, należy pogrupować wszystkie anagramy. Kluczowa obserwacja: anagramy mają taką samą posortowaną sekwencję znaków. Należy użyć defaultdict(list), którego kluczem jest posortowana krotka znaków napisu (krotki są haszowalne). Każda grupa jest gromadzona pod tym samym kluczem. Złożoność czasowa: O(n × L log L), gdzie L oznacza maksymalną długość napisu.
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 najczęściej występujących elementów (LeetCode 347)
LeetCode 347 „K najczęściej występujących elementów”: należy zwrócić k elementów o największej częstości. Bezpośrednie podejście ma złożoność O(n log n): zlicz częstości, posortuj je malejąco według częstości i pobierz pierwsze k elementów. Optymalne podejście O(n) wykorzystuje sortowanie kubełkowe: utwórz kubełki indeksowane częstością (od 1 do n), umieść każdy element w kubełku odpowiadającym jego częstości, a następnie przeglądaj kubełki od najwyższej do najniższej częstości, zbierając k elementów.
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]Sortowanie znaków według częstości (LeetCode 451)
LeetCode 451 „Sortowanie znaków według częstości”: należy przestawić napis tak, aby znaki występowały w kolejności malejącej według częstości. Zlicz częstości, posortuj znaki malejąco według częstości i połącz je. Użycie most_common jest najbardziej przejrzystym podejściem w Pythonie. Złożoność czasowa sortowania unikatowych znaków według częstości wynosi 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'Harmonogram zadań (LeetCode 621)
LeetCode 621 „Harmonogram zadań”: mając zadania i czas oczekiwania n, należy znaleźć minimalny czas potrzebny na ukończenie wszystkich zadań. Kluczowa obserwacja: struktura rozwiązania zależy od zadania występującego najczęściej. Należy rozmieścić max_count kopii najczęściej występującego zadania z (n) przerwami. Minimalny łączny czas = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Jeśli wystarczająca liczba różnych zadań wypełnia przerwy, czas bezczynności wynosi 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)) # 10Głosowanie większościowe za pomocą Counter
LeetCode 169 „Element większościowy”: należy znaleźć element występujący więcej niż n/2 razy. Chociaż głosowanie Boyera-Moore'a jest optymalnym rozwiązaniem z użyciem pamięci O(1), zastosowanie Counter.most_common(1) rozwiązuje problem bezpośrednio w czasie O(n) i przy użyciu pamięci O(n). Jeśli podczas rozmowy rekrutacyjnej wymagana jest pamięć O(1), należy przedstawić Boyer-Moore jako dalszą część rozwiązania; jeśli dodatkowa pamięć jest dozwolona, Counter jest prostszy.
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)) # 2Pierwszy niepowtarzający się znak
LeetCode 387 „Pierwszy unikatowy znak w napisie”: należy znaleźć indeks pierwszego znaku występującego dokładnie raz. Podejście dwuprzebiegowe: w pierwszym przebiegu buduje się zliczenie częstości, a w drugim znajduje się pierwszy znak o liczności 1. Złożoność czasowa: O(n), pamięciowa: O(1), ponieważ alfabet jest stały i obejmuje 26 znaków.
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')) # -1Suma podtablicy równa K (LeetCode 560)
LeetCode 560 „Suma podtablicy równa K”: należy zliczyć podtablice, których suma wynosi k. Podejście brutalne ma złożoność O(n²). Podejście O(n): należy utrzymywać bieżącą sumę prefiksową oraz mapę częstości dotychczas napotkanych sum prefiksowych. Dla każdej pozycji i liczba podtablic kończących się na i, których suma wynosi k, jest równa liczbie wcześniejszych sum prefiksowych równych (current_prefix_sum - k). Mapę należy zainicjalizować wartością {0: 1}, aby uwzględnić podtablice rozpoczynające się od indeksu 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)) # 4Działania arytmetyczne i część wspólna Counter
Counter obsługuje działania arytmetyczne: + scala elementy, dodając ich liczności, - odejmuje liczności i przycina wynik do 0, & wybiera minimum, tworząc część wspólną, a | wybiera maksimum, tworząc sumę. Działania te upraszczają problemy takie jak „znajdowanie wspólnych znaków w wielu napisach” lub „minimalna liczba znaków do usunięcia, aby jeden napis stał się anagramem drugiego”.
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())) # 5Podsumowanie: kiedy stosować zliczanie częstotliwości
Po zliczanie częstotliwości warto sięgnąć, gdy problem obejmuje: sprawdzenie, czy dwa napisy są równoważne po przestawieniu znaków (anagram), znalezienie najczęściej lub najrzadziej występujących elementów, sprawdzenie, czy kolekcja zawiera właściwy zestaw „składników”, albo przekształcenie problemu dotyczącego podtablicy lub podnapisu w problem sumy prefiksowej z mapą. Kluczowe jest to, że kolejność elementów w grupie nie ma znaczenia — liczą się tylko ich liczności.
Dla czytelności należy zawsze używać Counter; na zwykły dict lub tablicę warto przejść tylko wtedy, gdy potrzebna jest dokładniejsza kontrola albo ścisłe O(1) pamięci przy ograniczonym alfabecie.
Szybki test
Proszę sprawdzić znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: Counter zapewnia zliczanie częstości w O(n), obsługę most_common, operatorów arytmetycznych i dostęp z domyślną wartością zero, grupowanie według postaci kanonicznej (posortowanej krotki) rozwiązuje problem grupowania anagramów w O(nL log L), a suma prefiksowa z mapą częstości przekształca problem sumy podtablicy równej k z O(n²) w O(n). Następnie zajmiemy się problemem najdłuższego kolejnego ciągu i projektowaniem pamięci podręcznej LRU.
Często zadawane pytania
Czy lekcja „Zliczanie częstotliwości i grupowanie” jest bezpłatna?
Tak — pełny tekst „Zliczanie częstotliwości i grupowanie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Zliczanie częstotliwości i grupowanie”?
Wykorzystają Państwo Counter i defaultdict do zliczania częstotliwości znaków, grupowania anagramów według posortowanego klucza oraz znajdowania elementów o największej częstotliwości top-k. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Zliczanie częstotliwości i grupowanie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Wewnętrzne działanie funkcji haszującej i obsługa kolizji
- Two-Sum i jego liczne warianty
- Zliczanie częstotliwości i grupowanie
- Najdłuższy spójny ciąg i pamięć podręczna LRU