Top K Frequent Elements
Kamu mendapatkan sebuah array bilangan bulat nums dan sebuah bilangan bulat k. Kembalikan k nilai yang paling sering muncul dalam nums, dengan nilai yang paling sering muncul berada di urutan pertama. Jika dua nilai muncul dengan jumlah yang sama, nilai yang lebih kecil berada di urutan pertama.
Setiap nilai muncul satu kali dalam jawaban, seberapa sering pun nilai itu muncul dalam nums, dan k tidak pernah lebih besar daripada jumlah nilai yang berbeda.
Fungsi
- numsinteger-array
- nilai yang akan dihitung
- kinteger
- berapa banyak nilai yang dikembalikan
- Mengembalikaninteger-array
- k nilai yang paling sering muncul, diurutkan mulai dari yang paling sering. Jika frekuensinya sama, nilai yang lebih kecil diurutkan lebih dahulu.
Batasan
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ k, dankpaling banyak sama dengan jumlah nilai berbeda dalamnums.
Contoh
- Input
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Output
- [4, 1]
- Penjelasan
4muncul empat kali,1tiga kali, dan2serta3masing-masing satu kali. Dua nilai yang paling sering muncul adalah4, lalu1.
- Input
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Output
- [-2, 5]
- Penjelasan
-2,5, dan7masing-masing muncul dua kali, sedangkan9muncul satu kali. Tiga nilai berbagi posisi tertinggi, jadi dua nilai terkecil,-2dan5, adalah jawabannya.
- Input
- nums = [8]k = 1
- Output
- [8]
- Penjelasan
- Hanya ada satu nilai, jadi nilai itu paling sering muncul.
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Mulailah dengan mencari tahu seberapa sering setiap nilai muncul. Struktur data apa yang memetakan nilai ke jumlah kemunculannya dalam satu kali lintasan?
Dengan jumlah yang sudah diketahui, kamu ingin mendapatkan
knilai terbaik berdasarkan urutan tertentu: jumlah yang lebih besar didahulukan, lalu nilai yang lebih kecil jika jumlahnya sama. Mengurutkan setiap nilai yang berbeda bisa dilakukan. Min-heap berukurankhanya menyimpan nilai yang masih bisa menjadi bagian dari jawaban.Jumlah adalah bilangan bulat dari 1 hingga
n. Buat satu wadah untuk setiap jumlah, wadahcmenampung nilai yang muncul tepatckali, lalu baca wadah dari jumlah tertinggi ke terendah. Isi wadah dengan menelusuri nilai dari yang terkecil hingga terbesar, dan setiap wadah sudah berada dalam urutan saat terjadi seri.
Solusi
Satu kali pemindaian dengan hash map menghitung setiap nilai. Lalu pilih k nilai terbaik: mengurutkan semua d nilai yang berbeda membutuhkan biaya O(d log d), min-heap berukuran k membutuhkan biaya O(d log k), dan karena jumlah kemunculan berkisar dari 1 hingga n, bucket sort mengurutkan nilai berdasarkan jumlah kemunculannya tanpa perbandingan.
Hitung, lalu urutkan berdasarkan jumlah
Intuisi
Hitung dengan hash map: [4, 1, 4, 2, 1, 4, 3, 1, 4] menghasilkan 4 → 4, 1 → 3, 2 → 1, 3 → 1. Lalu urutkan nilai-nilai yang berbeda berdasarkan jumlah kemunculannya, dari yang terbanyak, lalu berdasarkan nilainya, dari yang terkecil. Perbandingan tersebut menentukan urutan jawaban, jadi k entri pertama adalah jawabannya.
Mengurutkan d nilai berbeda membutuhkan biaya O(d log d), sekitar 1.3 × 10^5 perbandingan untuk 10^4 nilai berbeda. Cara ini mengurutkan semua nilai meskipun hanya k nilai pertama yang diperlukan.
Algoritma
- Hitung setiap nilai dalam hash map.
- Masukkan nilai-nilai yang berbeda ke dalam list.
- Urutkan list berdasarkan jumlah dari yang terbesar ke terkecil, dan berdasarkan nilai dari yang terkecil ke terbesar jika jumlahnya sama.
- Kembalikan
knilai pertama.
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Most frequent first; equal counts put the smaller value first.
ordered = sorted(counts, key=lambda value: (-counts[value], value))
return ordered[:k]Simpan k terbaik dalam min-heap
Intuisi
Simpan hanya k kandidat. Nilai baru disimpan hanya jika mengungguli kandidat terlemah, yaitu kandidat dengan jumlah kemunculan lebih rendah, atau jumlah kemunculan yang sama dan nilai lebih besar. Min-heap yang diurutkan berdasarkan aturan itu menempatkan kandidat terlemah di posisi teratas, sehingga bisa dibaca dalam O(1) dan diganti dalam O(log k). Nilai yang tidak mengungguli kandidat teratas bisa dibuang, karena k nilai yang lebih baik sudah tersimpan.
Heap hanya terurut sebagian, dan operasi pop mengembalikan nilai terlemah terlebih dahulu, jadi tulis jawaban dari posisi terakhir ke posisi pertama. Proses pemilihan membutuhkan O(d log k), lebih cepat daripada mengurutkan ketika k jauh lebih kecil daripada d.
Algoritma
- Hitung setiap nilai dalam hash map.
- Untuk setiap nilai yang berbeda, masukkan nilai tersebut selama heap berisi kurang dari
knilai. - Setelah heap penuh, bandingkan nilai tersebut dengan nilai teratas, yaitu nilai terlemah yang dipertahankan. Jika nilai baru lebih kuat, letakkan di posisi teratas lalu lakukan sift down.
- Keluarkan nilai dari heap sebanyak
kkali, lalu tulis setiap nilai ke dalam jawaban dari posisi terakhir hingga pertama.
import heapq
from collections import Counter
def topKFrequent(nums, k):
counts = Counter(nums)
# Entries are (count, -value). heapq keeps the smallest entry on top, which is
# the weakest value kept: the lowest count, and on a tie the larger value.
heap = []
for value, count in counts.items():
heapq.heappush(heap, (count, -value))
if len(heap) > k:
heapq.heappop(heap)
# Pops come out weakest first, so fill the answer from the back.
result = [0] * k
for i in range(k - 1, -1, -1):
result[i] = -heapq.heappop(heap)[1]
return resultHitung, lalu urutkan berdasarkan jumlah
Intuisi
Jumlah adalah bilangan bulat dari 1 sampai n, jadi masukkan setiap nilai ke dalam wadah sesuai jumlah kemunculannya, lalu baca wadah mulai dari n ke bawah. Nilai akan keluar dengan yang paling sering muncul terlebih dahulu, dan tidak ada dua jumlah yang dibandingkan.
Untuk aturan jika seri, hitung dalam array yang berisi R = 2 × 10^4 + 1 penghitung, dengan nilai v pada indeks v + 10^4, lalu telusuri dari nilai terkecil ke atas sambil menambahkan setiap nilai ke wadahnya. Setiap wadah kemudian terisi dalam urutan menaik, yang menjadi urutan jika seri. Pada contoh kedua, penelusuran memasukkan -2, 5, 7 ke wadah 2, dan k = 2 mengambil -2 dan 5.
Secara keseluruhan, kompleksitasnya adalah O(n + R). Jika array diganti dengan hash map, wadah akan terisi sesuai urutan map dan masing-masing perlu diurutkan.
Algoritma
- Hitung setiap nilai dalam array yang diindeks dengan
value + 10^4. - Buat bucket 1 hingga
n, satu list untuk setiap jumlah yang mungkin. - Telusuri array penghitung dari nilai terkecil hingga terbesar, lalu tambahkan setiap nilai yang muncul ke bucket sesuai jumlah kemunculannya.
- Baca bucket dari jumlah
nturun hingga 1, ambil nilai sampai kamu mendapatkank.
def topKFrequent(nums, k):
OFFSET = 10000 # values run from -10^4 to 10^4
counts = [0] * (2 * OFFSET + 1)
for x in nums:
counts[x + OFFSET] += 1
# buckets[c] lists the values that occur exactly c times. Walking the
# values from smallest to largest fills every bucket in ascending order.
buckets = [[] for _ in range(len(nums) + 1)]
for i, c in enumerate(counts):
if c > 0:
buckets[c].append(i - OFFSET)
# Read the buckets from the highest count down until k values are taken.
result = []
for c in range(len(nums), 0, -1):
for value in buckets[c]:
result.append(value)
if len(result) == k:
return result
return result
Jebakan dan kasus tepi
- Memecahkan nilai yang seri berdasarkan kemunculan pertama atau urutan hash map. Pada contoh kedua,
-2,5, dan7semuanya muncul dua kali, dan hanya aturan nilai terkecil yang menghasilkan[-2, 5]. - Mengembalikan array heap apa adanya. Nilai teratasnya adalah nilai terlemah, yaitu nilai yang seharusnya berada paling akhir.
- Membalik aturan seri pada heap. Min-heap pada
(count, value)mengeluarkan nilai yang lebih kecil saat jumlahnya seri. Gunakan(count, -value). - Membuat bucket hanya sebanyak jumlah nilai yang berbeda. Dalam
[3, 3, 3, 3], satu nilai muncul sebanyaknkali, jadi bucketnharus tersedia. - Di Java, membandingkan dua jumlah
Integerdengan!=. Operator itu membandingkan referensi dan menyebabkan masalah saat jumlahnya melebihi 127.
Pertanyaan yang sering diajukan3
Berapa kompleksitas waktu Top K Frequent Elements?
Penghitungan membutuhkan O(n). Memilih k teratas membutuhkan O(d log d) dengan pengurutan atas d nilai berbeda, O(d log k) dengan min-heap berukuran k, dan satu kali penelusuran semua hitungan dengan bucket sort. Karena d dapat mencapai n, pengurutan membutuhkan O(n log n) dalam kasus terburuk, sedangkan bucket sort linear.
Bisakah Top K Frequent Elements diselesaikan dalam waktu O(n)?
Ya, dengan bucket sort, karena jumlahnya adalah bilangan bulat dari 1 hingga n. Quickselect pada jumlah juga O(n) secara rata-rata, tetapi kasus terburuknya bersifat kuadratik.
Mengapa menggunakan min-heap dan bukan max-heap?
Max-heap dari semua nilai d juga bisa digunakan: bangun max-heap dalam O(d) dan lakukan pop sebanyak k kali, totalnya O(d + k log d). Min-heap berukuran k hanya menampung k entri dan cocok untuk nilai yang datang satu per satu, karena elemen teratasnya adalah kandidat yang akan dibuang.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def topKFrequent(nums, k):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Output yang diharapkan
[4, 1]