Top K Frequent Elements
Problem (yeniden ifade)
Herhangi bir sırada k en sık elemanı döndür. Cevap tektir.
Sezgi
Frekansları say, sonra frekansa göre bucket’la ki en yoğun bucket’lar sonda olsun.
Yaklaşımlar
Frekans bucket'ları
DoğrulanmadıZaman O(n)Alan O(n)
Fikir. Değer→sayı map. buckets[c] sayısı c olan değerleri tutar. Bucket’ları yüksekten düşüğe tara.
Yürüyüş. [1,1,1,2,2,3], k=2 → 1’in freq’i 3, 2’nin 2 → [1,2].
Trade-off. Heap O(n log k). Frekans en fazla n olduğu için bucket taraması worst-case O(n).
Çözüm
export function topKFrequent(nums: number[], k: number): number[] {
const freq = new Map<number, number>();
for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [val, c] of freq) buckets[c]!.push(val);
const out: number[] = [];
for (let c = buckets.length - 1; c >= 0 && out.length < k; c--) {
for (const v of buckets[c]!) {
out.push(v);
if (out.length === k) return out;
}
}
return out;
}
export function topKFrequent(nums: number[], k: number): number[] {
const freq = new Map<number, number>();
for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [val, c] of freq) buckets[c]!.push(val);
const out: number[] = [];
for (let c = buckets.length - 1; c >= 0 && out.length < k; c--) {
for (const v of buckets[c]!) {
out.push(v);
if (out.length === k) return out;
}
}
return out;
}
Şablon bağlantısı
Hash map ile say, sonra frekansa göre kova (heap / quick-select de çalışır).
Yansıma
- Sıklık map’i + k boyutlu heap mi, kova (bucket) mi? En kötü sıklık n iken kova neden O(n)?
- Cevap tektir ama sıra serbest; testler sıraya bakıyor mu?
k = niken heap’in kazancı kalır mı?