Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Easyquick-select

Kth Largest Element in a Stream

Problem (yeniden ifade)

Tamsayı dizisi ve k ile tohumlanan bir yapı tasarla. Her add(val) val’i ekler ve şimdiye kadar görülenlerin k. en büyüğünü döndürür.

Sezgi

Akış hiç küçülmez, yalnızca en büyük k değer gerekir. Boyu k min-heap: kök k. en büyük. Yeni değer kökten büyükse yer değiştir. Quick select burada yanlış araç — çevrimdışı.

Yaklaşımlar

Boyu k min-heap

Doğrulanmadı

Zaman O(log k) addAlan O(k)

Fikir. Kurucu her tohumu add’den geçirir. add iter, size > k ise çeker, peek döndürür. k’den az değer geldiyse heap hepsini tutar (kısıtlar sorgu anında k’nin geçerli olduğunu garanti eder).

Yürüyüş. k=3, tohum [4,5,8,2]. Heap [4,5,8]. add 3 → hâlâ 4. add 5 → 5. add 10 → 5. add 9 → 8.

Trade-off. Akış top-K heap’tir, partition değil. LC 215 ile aynı boy-k min-heap, çağrılar boyunca yeniden kullanılır.

Çözüm

export class KthLargest {
  private k: number;
  private heap: number[] = [];

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) this.add(x);
  }

  add(val: number): number {
    this.heap.push(val);
    this.heap.sort((a, b) => a - b);
    if (this.heap.length > this.k) this.heap.shift();
    return this.heap[0]!;
  }
}

export class KthLargest {
  private k: number;
  private heap: number[] = [];

  constructor(k: number, nums: number[]) {
    this.k = k;
    for (const x of nums) this.add(x);
  }

  add(val: number): number {
    this.heap.push(val);
    this.heap.sort((a, b) => a - b);
    if (this.heap.length > this.k) this.heap.shift();
    return this.heap[0]!;
  }
}

Şablon bağlantısı

Quick Select sayfasındaki streaming top K: heap kökü yener. Quick select her add’de sıfırdan kurar.

Yansıma

k boyutlu min-heap. k’yı aşınca en küçüğü at. Tepe, görülenlerin k’ıncısı büyük.
İlk k eklemeden önce tepe henüz k’ıncı değil. Problem sorguyu ancak o kadar eklemeden sonra yapar.
Eşitler ayrı eleman. k = 1 akan maksimum. Eski küçükler tepeden düşer.