Conteggio e raggruppamento delle frequenze
Usi Counter e defaultdict per contare le frequenze dei caratteri, raggruppi gli anagrammi in base a una chiave ordinata e trovi gli elementi più frequenti con top-k
Conteggio e raggruppamento delle frequenze è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Conteggio delle frequenze: il pattern fondamentale
Il conteggio delle frequenze è uno dei pattern più versatili nei colloqui di programmazione. Contando quante volte compare ogni elemento in una lista o stringa, può rispondere a domande su duplicati, anagrammi, elementi più frequenti e disposizioni valide in tempo O(n), molto meglio dell'alternativa basata su ordinamento e scansione, che richiede O(n log n).
Counter e defaultdict(int) di Python sono gli strumenti standard. Entrambi creano una mappa da elemento a conteggio; Counter supporta inoltre le operazioni aritmetiche e 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)]Anagramma valido (LeetCode 242)
LeetCode 242 «Anagramma valido»: determini se due stringhe sono anagrammi l'una dell'altra. Due stringhe sono anagrammi se hanno le stesse frequenze di caratteri. Confronti i relativi oggetti Counter oppure ordini entrambe le stringhe. L'uso di Counter richiede O(n), mentre l'ordinamento richiede O(n log n). L'approccio con Counter è ottimale ed esprime direttamente la definizione.
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')) # TrueRaggruppare gli anagrammi (LeetCode 49)
LeetCode 49 «Raggruppare gli anagrammi»: data una lista di stringhe, raggruppi tutti gli anagrammi. L'idea chiave è che gli anagrammi hanno la stessa sequenza di caratteri ordinata. Usi un defaultdict(list) indicizzato dalla tupla ordinata della stringa (le tuple sono hashable). Ogni gruppo accumula gli elementi sotto la stessa chiave. Complessità temporale: O(n × L log L), dove L è la lunghezza massima di una stringa.
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())
Elementi più frequenti (LeetCode 347)
LeetCode 347 «Elementi più frequenti»: restituisca i k elementi più frequenti. Un approccio diretto richiede O(n log n): contare le frequenze, ordinare in base al conteggio decrescente e prendere i primi k elementi. L'approccio ottimale O(n) usa il bucket sort: crei dei bucket indicizzati per frequenza (da 1 a n), inserisca ogni elemento nel bucket corrispondente alla sua frequenza, quindi scansioni i bucket dalla frequenza più alta a quella più bassa raccogliendo k elementi.
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]Ordinare i caratteri in base alla frequenza (LeetCode 451)
LeetCode 451 «Ordinare i caratteri in base alla frequenza»: riorganizzi una stringa in modo che i caratteri compaiano in ordine decrescente di frequenza. Conti le frequenze, ordini i caratteri in base alla frequenza decrescente e concateni il risultato. L'uso di most_common è l'approccio Python più pulito. Complessità temporale: O(n log n) per ordinare i caratteri distinti in base alla frequenza.
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'Pianificatore di attività (LeetCode 621)
LeetCode 621 «Pianificatore di attività»: dati alcuni task e un cooldown n, trovi il tempo minimo necessario per completarli tutti. L'idea fondamentale è che il task più frequente determina la struttura. Disponga max_count copie del task più frequente con intervalli di (n) posizioni. Il tempo minimo totale = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Se ci sono abbastanza task diversi da riempire gli intervalli, il tempo inattivo è 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)) # 10Votazione a maggioranza con Counter
LeetCode 169 «Elemento maggioritario»: trovi l'elemento che compare più di n/2 volte. Sebbene la votazione di Boyer-Moore sia la soluzione ottimale con spazio O(1), l'uso di Counter.most_common(1) risolve direttamente il problema in tempo O(n) e con spazio O(n). Nei colloqui in cui viene richiesto spazio O(1), presenti Boyer-Moore come approfondimento; se è consentito usare spazio aggiuntivo, Counter è più semplice.
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)) # 2Primo carattere non ripetuto
LeetCode 387 «Primo carattere univoco in una stringa»: trovi l'indice del primo carattere che compare esattamente una volta. L'approccio in due passaggi è il seguente: il primo passaggio costruisce il conteggio delle frequenze; il secondo trova il primo carattere con conteggio pari a 1. Complessità temporale: O(n); spazio: O(1), poiché l'alfabeto è fisso e contiene 26 caratteri.
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')) # -1Somma del sottoarray uguale a K (LeetCode 560)
LeetCode 560 «Somma del sottoarray uguale a K»: conti i sottoarray la cui somma è k. La forza bruta richiede O(n²). L'approccio O(n) consiste nel mantenere una somma prefissa corrente e una mappa delle frequenze delle somme prefisse già osservate. Per ogni posizione i, il numero di sottoarray che terminano in i e hanno somma k equivale al numero di somme prefisse precedenti uguali a (current_prefix_sum - k). Inizializzi la mappa con {0: 1} per gestire i sottoarray che iniziano dall'indice 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)) # 4Operazioni aritmetiche e intersezione con Counter
Counter supporta le operazioni aritmetiche: + unisce i conteggi (sommandoli), - li sottrae (limitandoli a 0), & prende il minimo (intersezione) e | prende il massimo (unione). Queste operazioni semplificano problemi come «trovare i caratteri comuni in più stringhe» o «rimuovere il numero minimo di caratteri per rendere una stringa un anagramma dell'altra».
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())) # 5Riepilogo: quando usare il conteggio delle frequenze
Ricorra al conteggio delle frequenze quando il problema richiede di: verificare se due stringhe sono equivalenti a meno dell'ordine (anagrammi), trovare gli elementi più o meno frequenti, verificare che una raccolta contenga gli «ingredienti» corretti oppure trasformare un problema su sottoarray o sottostringhe in un problema di somma prefissa con mappa. Il punto chiave è che l'ordine all'interno di un gruppo non conta: contano solo le frequenze.
Usi sempre Counter per maggiore chiarezza; passi a un semplice dict o a un array solo quando ha bisogno di un controllo più preciso o di uno spazio strettamente O(1) con un alfabeto limitato.
Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: Counter fornisce il conteggio delle frequenze in O(n), con most_common, operatori aritmetici e accesso con valore predefinito pari a zero, il raggruppamento per forma canonica (tupla ordinata) risolve il problema del raggruppamento degli anagrammi in O(nL log L) e la somma prefissa con una mappa delle frequenze trasforma il problema della somma del sottoarray uguale a k da O(n²) a O(n). Nella prossima lezione affronteremo il problema della sequenza consecutiva più lunga e la progettazione di una cache LRU.
Domande Frequenti
La lezione «Conteggio e raggruppamento delle frequenze» è gratuita?
Sì — il testo completo di «Conteggio e raggruppamento delle frequenze» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Conteggio e raggruppamento delle frequenze»?
Usi Counter e defaultdict per contare le frequenze dei caratteri, raggruppi gli anagrammi in base a una chiave ordinata e trovi gli elementi più frequenti con top-k Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Conteggio e raggruppamento delle frequenze»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Interni delle funzioni hash e gestione delle collisioni
- Two-sum e le sue numerose varianti
- Conteggio e raggruppamento delle frequenze
- Sequenza consecutiva più lunga e cache LRU