Frekvenstelling og gruppering
Bruk Counter og defaultdict til å telle tegnfrekvenser, gruppere anagrammer etter sortert nøkkel og finne de hyppigste elementene med top-k.
Frekvenstelling og gruppering er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Frekvenstelling: kjernemønsteret
Frekvenstelling er blant de mest allsidige mønstrene i kodeintervjuer. Ved å telle hvor ofte hvert element forekommer i en liste eller streng, kan De besvare spørsmål om duplikater, anagrammer, de vanligste elementene og gyldige arrangementer med kjøretid O(n) — langt bedre enn alternativet med sortering og gjennomgang i O(n log n).
Python-klassene Counter og defaultdict(int) er standardverktøyene. Begge oppretter en mapping fra element til antall; Counter støtter i tillegg aritmetikk og 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)]Gyldig anagram (LeetCode 242)
LeetCode 242 «Valid Anagram»: avgjør om to strenger er anagrammer av hverandre. To strenger er anagrammer hvis de har samme tegnfrekvenser. Sammenlign Counter-objektene deres eller sorter begge strengene. Bruk av Counter gir O(n), mens sortering gir O(n log n). Counter-tilnærmingen er optimal og uttrykker definisjonen direkte.
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')) # TrueGrupper anagrammer (LeetCode 49)
LeetCode 49 «Group Anagrams»: gitt en liste med strenger skal De gruppere alle anagrammer sammen. Hovedideen er at anagrammer har samme sorterte tegnsekvens. Bruk en defaultdict(list) med nøkkel basert på den sorterte tuplen av strengen (tupler er hashbare). Hver gruppe samles under samme nøkkel. Kjøretid: O(n × L log L), der L er maksimal strenglengde.
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())
De k hyppigste elementene (LeetCode 347)
LeetCode 347 «Top K Frequent Elements»: returner de k hyppigste elementene. En direkte tilnærming har kjøretid O(n log n): tell frekvensene, sorter etter antall i synkende rekkefølge, og ta de første k. Den optimale tilnærmingen i O(n) bruker bøttesortering: opprett bøtter indeksert etter frekvens (1 til n), plasser hvert element i bøtten for frekvensen, og gå gjennom bøttene fra høyeste til laveste frekvens mens De samler inn k elementer.
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]Sorter tegn etter frekvens (LeetCode 451)
LeetCode 451 «Sort Characters By Frequency»: omorganiser en streng slik at tegnene forekommer i synkende frekvensrekkefølge. Tell frekvensene, sorter tegnene etter synkende frekvens, og sett dem sammen. Bruk av most_common er den ryddigste Python-tilnærmingen. Kjøretid: O(n log n) for sortering av de unike tegnene etter frekvens.
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'Oppgaveplanlegger (LeetCode 621)
LeetCode 621 «Task Scheduler»: gitt oppgaver og en nedkjølingstid n skal De finne den minste tiden det tar å fullføre alle oppgavene. Den avgjørende innsikten er at den hyppigste oppgaven bestemmer strukturen. Plasser max_count kopier av den hyppigste oppgaven med (n) mellomrom. Total minimumstid = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Hvis det finnes nok ulike oppgaver til å fylle mellomrommene, er inaktiv tid lik 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)) # 10Flertallsvalg med Counter
LeetCode 169 «Majority Element»: finn elementet som forekommer mer enn n/2 ganger. Selv om Boyer-Moore voting er den optimale løsningen med O(1) plassbruk, løser Counter.most_common(1) problemet direkte med O(n) kjøretid og O(n) plassbruk. Hvis intervjuet krever O(1) plassbruk, bør De presentere Boyer-Moore som en oppfølging; hvis ekstra plass er tillatt, er Counter enklere.
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)) # 2Første tegn som ikke gjentas
LeetCode 387 «First Unique Character in a String»: finn indeksen til det første tegnet som forekommer nøyaktig én gang. En tilnærming i to gjennomganger: Første gjennomgang bygger en frekvenstelling; den andre finner det første tegnet med antall 1. Kjøretid: O(n), plassbruk: O(1), siden alfabetet er fast og består av 26 tegn.
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')) # -1Deltabell med sum lik K (LeetCode 560)
LeetCode 560 «Subarray Sum Equals K»: tell deltabeller med sum k. Brute force gir O(n²). Tilnærmingen i O(n) er å opprettholde en løpende prefikssum og et frekvenskart over prefikssummer som er sett så langt. For hver posisjon i er antallet deltabeller som slutter ved i og har sum k lik antallet tidligere prefikssummer som er lik (current_prefix_sum - k). Initialiser kartet med {0: 1} for å håndtere deltabeller som starter på indeks 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)) # 4Counter: aritmetikk og snitt
Counter støtter aritmetikk: + slår sammen (legger sammen antall), - trekker fra (avgrenser ved 0), & tar minimumsverdien (snitt), og | tar maksimumsverdien (union). Disse operasjonene forenkler problemer som «finn felles tegn i flere strenger» eller «fjern minst mulig tegn for å gjøre én streng til et anagram av en annen».
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())) # 5Oppsummering: Når bør De bruke frekvenstelling
Bruk frekvenstelling når problemet innebærer å kontrollere om to strenger er like opptil omorganisering (anagrammer), finne de mest eller minst vanlige elementene, kontrollere at en samling har de riktige «ingrediensene», eller gjøre et problem med deltabeller eller delstrenger om til et problem med prefikssum og map. Hovedpoenget er at rekkefølgen innad i en gruppe ikke spiller noen rolle — det er bare antallene som teller.
Bruk alltid Counter for tydelighetens skyld; bytt til en vanlig dict eller tabell bare når De trenger finere kontroll eller strengt O(1) plassbruk med et avgrenset alfabet.
Hurtigsjekk
Test forståelsen Deres av konseptene innen Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: Counter gir frekvenstelling i O(n) med most_common, aritmetiske operatorer og oppslag med standardverdien null, gruppering etter kanonisk form (sortert tuppel) løser group-anagrams i O(nL log L), og prefikssum med frekvensmap gjør problemet med deltabellsum lik k om fra O(n²) til O(n). Neste tema er problemet med den lengste sammenhengende sekvensen og utforming av LRU-cache.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Frekvenstelling og gruppering» gratis?
Ja – hele teksten i «Frekvenstelling og gruppering» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Frekvenstelling og gruppering»?
Bruk Counter og defaultdict til å telle tegnfrekvenser, gruppere anagrammer etter sortert nøkkel og finne de hyppigste elementene med top-k. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Frekvenstelling og gruppering»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Interne detaljer i hashfunksjoner og kollisjonshåndtering
- Two-Sum og de mange variantene
- Frekvenstelling og gruppering
- Lengste sammenhengende sekvens og LRU-cache