En sık geçen K eleman

Problem

Bir tamsayı dizisi ve bir k değeri veriliyor. Dizide en sık geçen k farklı değeri döndür. Cevabın tek olduğu garanti ediliyor (k. sıradaki frekansta eşitlik yok); sonucun sırası önemli değil. Beklenti, O(n log n)'den daha iyi bir çözüm.

Girdi:  nums = [7, 3, 7, 5, 3, 7, 9, 3, 7], k = 2
Çıktı:  [7, 3]        (7: 4 kez, 3: 3 kez, 5 ve 9: 1 kez)

Girdi:  nums = [4], k = 1
Çıktı:  [4]

Netleştirme soruları

• k, farklı eleman sayısından büyük olabilir mi? (Garanti yoksa: hepsini mi döndürmeli?)
• Eşit frekanslarda hangisi seçilmeli? (LeetCode'da cevap tek; gerçek bir sistemde deterministik bir ikinci kriter gerekir.)
• Sonuç frekansa göre sıralı mı olmalı?
• n ve farklı değer sayısı m ne kadar? Veri belleğe sığıyor mu, yoksa stream mi?

İpuçları

Yaklaşım

Adım 1, sayma: HashMap.merge(num, 1, Integer::sum) ile O(n). Bu adım her yaklaşımda ortak.

Brute force, sırala: Map girdilerini frekansa göre azalan sırala, ilk k'yı al. O(n + m log m). m küçükse en okunaklı çözüm budur ve mülakatta başlangıç olarak söylenmeli.

Boyutu k olan min-heap: Girdileri frekansa göre bir min-heap'e ekle; boyut k'yı aşarsa tepeyi (en az sık olanı) at. Sonunda heap'te en sık k eleman kalır. O(n + m log k) zaman, O(m + k) bellek. Heap'in tepesinde atılacak aday durur; bu yüzden en sık olanları bulmak için min-heap kullanılır. Bu, en sık yapılan kavram hatasıdır. k ≪ m olduğunda (ör. 10 milyon farklı değer içinde top 10) sıralamaya göre belirgin kazanç sağlar ve veri stream olarak geldiğinde de çalışır.

Bucket sort, O(n): Frekans 1 ile n arasında olduğu için buckets[frekans] listesine değerleri koy, en yüksek frekanstan başlayarak k değer topla. Sayma O(n), kovaları doldurma O(m), tarama O(n). Bellek O(n). Frekans üst sınırının n olması bu yöntemi mümkün kılan kilit gözlemdir.

Quickselect: Frekans dizisi üzerinde k. en büyüğü quickselect ile bul; ortalama O(m), en kötü O(m²) (rastgele pivot ile olasılıksal olarak önlenir). Sonuç sırasızdır ve dizi yerinde değişir.

Kodda bucket versiyonunu ana çözüm, heap versiyonunu ikinci metot olarak yazdım; testler ikisini de doğruluyor.

Java çözümü

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public final class TopKFrequentElements {

    // Bucket: frekans en fazla n olabilir; index = frekans. O(n) zaman.
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequency = countFrequencies(nums);
        List<List<Integer>> buckets = new ArrayList<>(nums.length + 1);
        for (int i = 0; i <= nums.length; i++) {
            buckets.add(new ArrayList<>());
        }
        frequency.forEach((value, count) -> buckets.get(count).add(value));

        int[] result = new int[Math.max(0, Math.min(k, frequency.size()))];
        int filled = 0;
        for (int count = nums.length; count > 0 && filled < result.length; count--) {
            for (int value : buckets.get(count)) {
                if (filled == result.length) {
                    break;
                }
                result[filled++] = value;
            }
        }
        return result;
    }

    // Boyutu k olan min-heap: O(n + m log k). Stream / sınırsız değer aralığı için genelleşir.
    public int[] topKFrequentWithHeap(int[] nums, int k) {
        Map<Integer, Integer> frequency = countFrequencies(nums);
        PriorityQueue<Map.Entry<Integer, Integer>> leastFrequentOnTop =
                new PriorityQueue<>(Map.Entry.comparingByValue());
        for (Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
            leastFrequentOnTop.offer(entry);
            if (leastFrequentOnTop.size() > k) {
                leastFrequentOnTop.poll();                         // en az sıklıktaki aday elenir
            }
        }
        int[] result = new int[leastFrequentOnTop.size()];
        for (int i = result.length - 1; i >= 0; i--) {
            result[i] = leastFrequentOnTop.poll().getKey();        // heap kötüden iyiye boşalır
        }
        return result;
    }

    private static Map<Integer, Integer> countFrequencies(int[] nums) {
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int num : nums) {
            frequency.merge(num, 1, Integer::sum);
        }
        return frequency;
    }
}

Bucket versiyonunda sonuç dizisi min(k, farklı değer sayısı) boyutunda: k farklı değer sayısından büyükse tüm değerler döner, k <= 0 ise boş dizi. Heap versiyonu da aynı sözleşmeye uyar. Her iki versiyon sonucu frekansa göre azalan sırada döndürür (eşit frekanslılar arasında sıra belirsiz).

Karmaşıklık

m: farklı değer sayısı (m ≤ n).

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı. Eşit frekanslarda birden fazla doğru cevap olabildiği için rastgele testte (3.000 girdi, 0-29 eleman, 8 farklı değer, k 1-6) birebir eşitlik yerine şu özellikler kontrol edildi: sonuç boyutu min(k, m), elemanlar farklı ve sonuçtaki frekansların azalan sıralı listesi, tüm frekansların azalan sıralı listesinin ilk min(k, m) elemanına eşit. İki versiyon da ayrı ayrı test edildi.

Mülakatçı için

Top-K ailesinin temel sorusu; backend karşılığı "en çok satan ürünler", "en çok hata veren endpoint'ler". Gözlenecek noktalar: adayın sayma ile seçmeyi iki aşama olarak ayırması, heap'in yönünü (min-heap) doğru gerekçelendirmesi ve karmaşıklığı n, m, k ile ayrı ayrı ifade etmesi. Bucket fikrini bulan aday ekstra puan alır ama zorunlu değildir; heap çözümü çoğu şirkette yeterli kabul edilir.

İpucu zamanlaması: Aday sıralamayla bitirirse "k çok küçük ve m çok büyükse?" diye sor. Max-heap'e her şeyi koyup k kez poll ederse doğru ama O(m log m) olduğunu fark etmesini bekle; min-heap'i öner. Zaman kalırsa üçüncü ipucuyla bucket'a yönlendir.

Takip soruları:

1. Veri sonsuz bir stream ve bellek sınırlı; son 1 saatin en sık 10 değeri her dakika raporlanacak. (Beklenen: dakikalık kovalar + kayan pencere; bellek sınırı aşılırsa Count-Min Sketch + küçük heap ya da Space-Saving algoritması; yaklaşık sonuç kabulü.)
2. Eşit frekanslarda küçük değer önce gelsin (deterministik). (Beklenen: heap comparator'ına ikinci kriter: tepede frekansı küçük, eşitlikte değeri büyük olan.)
3. Veri 100 sunucuya dağılmış. Her sunucu kendi top 10'unu gönderirse global top 10 doğru olur mu? (Beklenen: hayır; bir değer her sunucuda 11. olup toplamda 1. olabilir. Tam sayımları değere göre bölümleyip (shuffle) birleştirmek gerekir.)

Benzer problemler

• Top K Frequent Words (LeetCode 692): eşitlikte alfabetik sıra.
• Kth Largest Element in an Array (LeetCode 215): quickselect / heap.
• Sort Characters By Frequency (LeetCode 451): bucket.
• K Closest Points to Origin (LeetCode 973): boyutu k heap.
• Find Median from Data Stream (LeetCode 295) (bu sette: find-median-from-data-stream).