Penghitungan Frekuensi dan Pengelompokan
Gunakan Counter dan defaultdict untuk menghitung frekuensi karakter, mengelompokkan anagram berdasarkan kunci terurut, dan menemukan elemen dengan frekuensi top-k.
Penghitungan Frekuensi dan Pengelompokan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Penghitungan Frekuensi: Pola Inti
Penghitungan frekuensi adalah salah satu pola paling serbaguna dalam wawancara pemrograman. Dengan menghitung berapa kali setiap elemen muncul dalam daftar atau teks, Anda dapat menjawab pertanyaan tentang duplikat, anagram, elemen yang paling sering muncul, dan susunan yang valid dalam waktu O(n) — jauh lebih baik daripada alternatif pengurutan lalu pemindaian O(n log n).
Counter dan defaultdict(int) milik Python adalah alat standar. Keduanya membuat pemetaan dari elemen ke jumlah kemunculannya; Counter juga mendukung operasi aritmetika dan 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)]Anagram yang Valid (LeetCode 242)
LeetCode 242 'Anagram yang Valid': tentukan apakah dua teks merupakan anagram satu sama lain. Dua teks merupakan anagram jika memiliki frekuensi karakter yang sama. Bandingkan objek Counter-nya atau urutkan kedua teks. Menggunakan Counter membutuhkan O(n), sedangkan pengurutan membutuhkan O(n log n). Pendekatan Counter adalah yang paling optimal dan secara langsung menyatakan definisinya.
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')) # TrueKelompokkan Anagram (LeetCode 49)
LeetCode 49 'Kelompokkan Anagram': diberikan daftar teks, kelompokkan semua anagram secara bersamaan. Gagasan utamanya: anagram memiliki urutan karakter terurut yang sama. Gunakan defaultdict(list) dengan kunci berupa tuple terurut dari teks tersebut (tuple dapat di-hash). Setiap kelompok terakumulasi di bawah kunci yang sama. Waktu: O(n × L log L), dengan L sebagai panjang teks maksimum.
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 Elemen dengan Frekuensi Tertinggi (LeetCode 347)
LeetCode 347 'K Elemen dengan Frekuensi Tertinggi': kembalikan k elemen yang paling sering muncul. Pendekatan langsung membutuhkan O(n log n): hitung frekuensi, urutkan berdasarkan frekuensi secara menurun, lalu ambil k elemen pertama. Pendekatan optimal O(n) menggunakan pengurutan keranjang: buat keranjang yang diindeks berdasarkan frekuensi (1 hingga n), tempatkan setiap elemen ke keranjang frekuensinya, lalu telusuri keranjang dari frekuensi tertinggi ke terendah sambil mengumpulkan k elemen.
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]Urutkan Karakter berdasarkan Frekuensi (LeetCode 451)
LeetCode 451 'Urutkan Karakter berdasarkan Frekuensi': susun ulang teks agar karakter muncul berdasarkan frekuensi yang menurun. Hitung frekuensi, urutkan karakter berdasarkan frekuensi secara menurun, lalu gabungkan. Menggunakan most_common adalah pendekatan Python yang paling sederhana. Waktu: O(n log n) untuk mengurutkan karakter unik berdasarkan frekuensinya.
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'Penjadwal Tugas (LeetCode 621)
LeetCode 621 'Penjadwal Tugas': diberikan sejumlah tugas dan waktu jeda n, temukan waktu minimum untuk menyelesaikan semua tugas. Gagasan pentingnya: tugas yang paling sering muncul menentukan strukturnya. Susun salinan max_count dari tugas yang paling sering muncul dengan (n) jeda. Waktu minimum total = max((max_count - 1) * (n + 1) + num_tasks_with_max_count, total_tasks). Jika ada cukup banyak tugas berbeda untuk mengisi jeda, waktu menganggur adalah 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)) # 10Pemungutan Suara Mayoritas dengan Counter
LeetCode 169 'Elemen Mayoritas': temukan elemen yang muncul lebih dari n/2 kali. Meskipun pemungutan suara Boyer-Moore adalah solusi optimal dengan ruang O(1), penggunaan Counter.most_common(1) menyelesaikan masalah ini secara langsung dalam waktu O(n) dan ruang O(n). Untuk wawancara yang menyebutkan ruang O(1), sampaikan Boyer-Moore sebagai tindak lanjut; untuk wawancara yang mengizinkan ruang tambahan, Counter lebih sederhana.
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)) # 2Karakter Pertama yang Tidak Berulang
LeetCode 387 'Karakter Unik Pertama dalam Teks': temukan indeks karakter pertama yang muncul tepat satu kali. Pendekatan dua lintasan: lintasan pertama membuat hitungan frekuensi; lintasan kedua menemukan karakter pertama dengan jumlah 1. Waktu: O(n), Ruang: O(1) karena alfabetnya tetap terdiri dari 26 karakter.
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')) # -1Jumlah Sublarik Sama dengan K (LeetCode 560)
LeetCode 560 'Jumlah Sublarik Sama dengan K': hitung sublarik yang jumlahnya sama dengan k. Cara coba semua kemungkinan membutuhkan O(n²). Pendekatan O(n): pertahankan jumlah prefiks berjalan dan peta frekuensi jumlah prefiks yang telah terlihat. Untuk setiap posisi i, jumlah sublarik yang berakhir di i dengan jumlah k sama dengan jumlah jumlah prefiks sebelumnya yang sama dengan (current_prefix_sum - k). Inisialisasi peta dengan {0: 1} untuk menangani sublarik yang dimulai dari 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)) # 4Operasi Aritmetika dan Irisan Counter
Counter mendukung operasi aritmetika: + menggabungkan (menjumlahkan hitungan), - mengurangkan (membatasi hasil minimum pada 0), & mengambil nilai minimum (irisan), dan | mengambil nilai maksimum (gabungan). Operasi-operasi ini menyederhanakan masalah seperti 'menemukan karakter yang sama dalam beberapa teks' atau 'menghapus jumlah karakter minimum agar satu teks menjadi anagram dari teks lainnya'.
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())) # 5Ringkasan: Kapan Menggunakan Penghitungan Frekuensi
Gunakan penghitungan frekuensi ketika masalahnya melibatkan: pemeriksaan apakah dua teks setara jika urutannya diubah (anagram), pencarian elemen yang paling sering atau paling jarang muncul, validasi bahwa suatu koleksi memiliki 'bahan' yang tepat, atau pengubahan masalah sublarik/subteks menjadi masalah jumlah-prefiks-dengan-peta. Intinya, urutan di dalam suatu kelompok tidak penting — yang penting hanyalah jumlah kemunculannya.
Selalu gunakan Counter demi kejelasan; beralihlah ke dict biasa atau larik hanya jika Anda memerlukan kendali yang lebih terperinci atau ruang O(1) yang ketat dengan alfabet terbatas.
Pemeriksaan Singkat
Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rekapitulasi Pelajaran
Dalam pelajaran ini Anda mempelajari: Counter menyediakan penghitungan frekuensi O(n) dengan most_common, operator aritmetika, dan akses dengan nilai bawaan nol, pengelompokan berdasarkan bentuk kanonik (tuple terurut) menyelesaikan pengelompokan anagram dalam O(nL log L), dan jumlah-prefiks dengan peta frekuensi mengubah masalah jumlah-sublarik-k dari O(n²) menjadi O(n). Selanjutnya kita akan membahas masalah rangkaian berurutan terpanjang dan desain tembolok LRU.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Penghitungan Frekuensi dan Pengelompokan” gratis?
Ya — teks lengkap “Penghitungan Frekuensi dan Pengelompokan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Penghitungan Frekuensi dan Pengelompokan”?
Gunakan Counter dan defaultdict untuk menghitung frekuensi karakter, mengelompokkan anagram berdasarkan kunci terurut, dan menemukan elemen dengan frekuensi top-k. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Penghitungan Frekuensi dan Pengelompokan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Internal Fungsi Hash dan Penanganan Tabrakan
- Two-Sum dan Berbagai Variasinya
- Penghitungan Frekuensi dan Pengelompokan
- Urutan Berurutan Terpanjang dan Cache LRU