Top K Frequent Elements
Bir tamsayı dizisi nums ve bir tamsayı k veriliyor. nums içinde en sık görülen k değeri, en sık görülen başta olacak şekilde döndürün. İki değer aynı sayıda görülüyorsa küçük olan değer önce gelir.
Bir değer, nums içinde kaç kez görülürse görülsün yanıtta yalnızca bir kez yer alır ve k hiçbir zaman farklı değerlerin sayısından büyük olmaz.
Fonksiyon
- numsinteger-array
- sayılacak değerler
- kinteger
- kaç değer döndürüleceği
- Döndürürinteger-array
- en sık görülen k değer, en sık görülenler önce, eşitlik durumunda küçük değer önce
Kısıtlar
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ kvek,numsiçindeki farklı değerlerin sayısından en fazla olabilir.
Örnekler
- Girdi
- nums = [4, 1, 4, 2, 1, 4, 3, 1, 4]k = 2
- Çıktı
- [4, 1]
- Açıklama
4dört kez,1üç kez,2ve3ise birer kez geçer. En sık görülen iki değer, önce4, ardından1'dir.
- Girdi
- nums = [5, -2, 7, -2, 7, 5, 9]k = 2
- Çıktı
- [-2, 5]
- Açıklama
-2,5ve7değerlerinin her biri iki kez,9ise bir kez geçer. En yüksek sıklıkta üç değer eşit olduğundan, bunların en küçük ikisi olan-2ve5cevaptır.
- Girdi
- nums = [8]k = 1
- Çıktı
- [8]
- Açıklama
- Tek bir değer vardır, bu nedenle en sık görülen değerdir.
Gönderirken +16 gizli test
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Önce her değerin ne sıklıkta bulunduğunu öğren. Tek geçişte bir değeri sayısına eşleyen veri yapısı hangisidir?
Sayılar elindeyken, tek bir sıralamaya göre en iyi
kdeğeri istiyorsun: önce sayısı daha yüksek olan, eşitlik durumunda ise değeri daha küçük olan. Her farklı değeri sıralamak işe yarar.kboyutunda bir min-yığın, yanıtta hâlâ yer alabilecek değerleri tutar.Sayım, 1 ile
narasında bir tam sayıdır. Her sayım için bir kova oluştur;ckovası tam olarakckez görünen değerleri tutar ve kovaları en yüksek sayıdan aşağıya doğru oku. Kovaları değerleri küçükten büyüğe doğru gezerek doldur; böylece her kova eşitlik durumunda zaten doğru sıradadır.
Çözüm
Sayma kolay kısımdır: bir hash map üzerinde tek geçiş, her değerin sayısını verir. Asıl soru, gerekenden fazla iş yapmadan en iyi k değeri nasıl seçeceğindir. d farklı değerin tümünü sayıya göre sıralamak O(d log d) maliyetindedir; boyutu k olan bir min-heap bunu O(d log k) değerine düşürür ve sayı 1 ile n arasında bir tam sayı olduğundan, bucket sort değerleri sayıya göre hiçbir karşılaştırma yapmadan sıralar.
Say, ardından sayıya göre sırala
Sezgi
Önce say. Değerden sayıya eşleme yapan bir hash map ile tek geçişte [4, 1, 4, 2, 1, 4, 3, 1, 4] dizisi 4 → 4, 1 → 3, 2 → 1, 3 → 1 hâline gelir.
Ardından farklı değerleri yanıttaki sıraya koy: sayısı yüksek olan önce, sayıları eşitse küçük değer önce. Sıralamaya tam olarak bu karşılaştırmayı ver: ilk anahtar olarak sayıyı, ikinci olarak değeri kullan; sıralı listenin ilk k girdisi yanıttır. Buradaki sıralama 4, 1, 2, 3 olur ve k = 2, 4 ile 1 değerlerini tutar.
Sayma işleminin maliyeti O(n)'dir. d farklı değeri sıralamanın maliyeti O(d log d)'dir; her değer farklı olduğunda bu, en fazla O(n log n) olur: 10^4 değer yaklaşık 1.3 × 10^5 karşılaştırma gerektirir; bu da hızlıdır. Gereksiz olan, yalnızca ilk k değer önemliyken sıralamanın tüm değerleri sıralamasıdır.
Algoritma
- Bir hash map'teki her değeri sayın.
- Farklı değerleri bir listeye koyun.
- Listeyi sayıya göre azalan sırada, sayılar eşit olduğunda değere göre artan sırada sıralayın.
- İlk
kdeğeri döndürün.
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]En iyi k öğeyi bir min-heap'te tutun
Sezgi
Yalnızca en iyi k değere ihtiyacın var, bu yüzden yalnızca k aday tut. Her yeni değer için soru, elindeki en zayıf adayı geçip geçmediğidir; daha zayıf, daha düşük sayım ya da aynı sayım ve daha büyük değer demektir. Bu kurala göre sıralanmış bir min-yığın, en zayıf adayı en üstte tutar; böylece onu O(1) zamanda okuyabilir ve O(log k) zamanda değiştirebilirsin.
Birbirinden farklı değerleri dolaş. Yığın k değerinden az tuttuğu sürece değeri ekle. Bundan sonra, en üstteki değeri geçen bir değer onun yerine geçer; geçemeyen bir değer ise elenir, çünkü daha iyi olan k değer zaten tutuluyordur. Bir kütüphane yığınıyla her değeri ekleyip yığın k sınırını aştığında bir kez çıkarmak daha kısadır; bu işlem aynı k değeri tutar.
Sonunda yığın yanıtı tutar, ancak yanıt sırasıyla değil: yığın yalnızca kısmen sıralıdır. Çıkarma işlemi önce en zayıf değeri döndürür; bu yüzden yanıtı son konumdan ilk konuma doğru yaz.
Birbirinden farklı d değerin her biri, k öğeli yığında en fazla bir işlem gerektirir; bu yüzden seçim O(d log k) sürer. k, d'den çok daha küçük olduğunda (örneğin birbirinden farklı 8000 değerin en iyi 10'unu bulurken) bu yöntem sıralamadan daha hızlıdır.
Algoritma
- Bir hash map'teki her değeri sayın.
- Her farklı değer için, yığında
kdeğerinden az değer varken değeri yığına ekleyin. - Yığın dolduğunda, değeri en üstteki, yani tutulan en zayıf değerle karşılaştırın. Yeni değer daha güçlüyse, onu en üste koyun ve aşağı doğru eleyin.
- Yığını
kkez çıkarın ve her değeri sondan başa doğru yanıta yazın.
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 resultSayıya göre say, sonra kovaya göre sırala
Sezgi
Bir sayım herhangi bir sayı değildir: 1 ile n arasında bir tam sayıdır. Bu da bir kova sıralamasını mümkün kılar. Her sayım için bir kova oluştur; c kovasında tam olarak c kez görünen değerler yer alsın ve kovaları n numaralı kovadan aşağı doğru oku. Değerler en sık görünenden başlayarak çıkar ve hiçbir iki sayım karşılaştırılmaz.
Eşitlik kuralı bir şey daha gerektirir: bir kovanın içinde küçük değer önce gelmelidir. Değerler -10^4 ile 10^4 arasında olduğundan, sayımı R = 2 × 10^4 + 1 sayaçtan oluşan bir diziyle yapabiliriz; v değeri, v + 10^4 indeksinde bulunur. Bu diziyi en küçük değerden en büyük değere doğru dolaş ve her değeri kendi sayımına ait kovaya ekle. Her kova artan sırada dolar; bu da eşitlik durumundaki sıralamadır, dolayısıyla hiçbir şeyi sıralamak gerekmez.
[5, -2, 7, -2, 7, 5, 9] için dolaşım, -2, 5, 7 değerlerini bu sırayla 2 numaralı kovaya, 9 değerini ise 1 numaralı kovaya yerleştirir. 7 numaralı kovadan aşağı doğru okurken değer içeren ilk kova 2 numaralı kovadır ve k = 2, -2 ile 5 değerlerini alır.
İşlem; nums üzerinde bir geçiş, R sayaç üzerinde bir geçiş ve kovalar üzerinde bir geçişten oluşur; toplamda O(n + R) olur: sabit bir değer aralığı için doğrusaldır. Sayım dizisi yerine bir hash map kullanıldığında sayım yine doğrusal kalır, ancak kovalar haritanın sırasına göre dolar ve eşitlik kuralına uymak için her kovayı sıralaman gerekir.
Algoritma
value + 10^4ile indekslenen bir dizideki her değeri sayın.- 1'den
n'ye kadar, her olası sayı için bir liste olacak şekilde kovalar oluşturun. - Sayım dizisini en küçük değerden en büyük değere doğru tarayın ve görünen her değeri, sayısının karşılık geldiği kovaya ekleyin.
kdeğerine ulaşana kadar değerleri alarak kovaları sayın'den 1'e doğru okuyun.
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
Tuzaklar ve uç durumlar
Sayım nadiren yanlıştır. Yanıtın sırası ise öyle olabilir.
- Eşitlikleri ilk görülme sırasına veya hash map sırasına göre bozmak. İkinci örnekte
-2,5ve7değerlerinin tümü ikişer kez geçer ve[-2, 5]değerini tek doğru yanıt yapan yalnızca küçük değer kuralıdır. - Yığının dizisini olduğu gibi döndürmek. Bir yığın yalnızca kısmen sıralıdır ve tepesindeki değer en zayıf değerdir; yani en sona ait olandır.
- Yığının eşitlik kuralını ters uygulamak. Sayımları aynı olan iki değerden büyük olanı daha zayıftır; bu nedenle
(count, value)üzerinde bir min-heap kullanmak yanlış değeri çıkarır.(count, -value)kullanın veya kurala uygun bir karşılaştırma yazın. - Farklı değerlerin sayısı kadar kova oluşturmak. Bir değer,
[3, 3, 3, 3]örneğinde olduğu gibinkez geçebilir; bu nedenlennumaralı kova da bulunmalıdır. - Java'da iki
Integersayımını!=ile karşılaştırmak. Bu, referansları karşılaştırır ve sayımlar 127'yi geçince sorun çıkarır. Önce bunlarıinttürüne dönüştürün. - Sonunda bir kovanın tamamını almak. Bir kovanın ortasında olsanız bile
kdeğere ulaşır ulaşmaz durun.
Sıkça sorulan sorular4
En Sık Görülen K Eleman probleminin zaman karmaşıklığı nedir?
Sayma işlemi O(n) sürer. En üstteki k değeri seçmek ise d farklı değer üzerinde sıralama yapıldığında O(d log d), boyutu k olan bir min-heap kullanıldığında O(d log k) ve değer aralığında tek geçiş yapan kova sıralamasıyla O(n) maliyetindedir. d, n değerine ulaşabildiğinden, en kötü durumda sıralama O(n log n) sürer ve kova sıralaması doğrusaldır.
En Sık Görülen K İlk Öğe O(n) zamanda çözülebilir mi?
Evet, kova sıralamasıyla. Sayılar 1 ile n arasında tam sayılardır; bu nedenle her değer, sayımına karşılık gelen kovaya yerleştirilir ve kovaları en yüksek sayıdan en düşüğe doğru okuyarak değerler frekanslarına göre, herhangi bir karşılaştırmalı sıralama yapmadan listelenir. Sayımlar üzerinde Quickselect de ortalama olarak O(n) sürede çalışır, ancak en kötü durumdaki karmaşıklığı kareseldir.
Neden max-heap değil de min-heap kullanılır?
Tüm d değerlerinden oluşan bir max-heap de işe yarar: O(d) sürede oluşturulur ve k kez çıkarma yapılır; toplamda O(d + k log d) olur. Boyutu k olan bir min-heap yalnızca k öğe tutar ve değerler teker teker geldiğinde uygundur; çünkü tepesindeki öğe çıkarılacak adaydır. Bunun bedeli, sonucu tersten vermesidir; bu nedenle sonucu sondan başlayarak doldurursun.
En Sık Görülen K Öğeyi bulurken eşitlikleri nasıl bozarsınız?
Bir kural seç ve bunu her yerde uygula; burada eşit sayılar olduğunda küçük değer önce gelir, bu da yanıtı benzersiz kılar. Sıralamada önce sayıları, ardından değerleri karşılaştır. Yığında, sayıları eşit olan iki değerden büyük olanı daha zayıftır. Kova sıralamasında kovaları değerleri artan sırada doldur; her kova zaten eşitlik sırasındadır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def topKFrequent(nums, k):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [4, 1, 4, 2, 1, 4, 3, 1, 4] k = 2
Beklenen
[4, 1]