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

Hardheap-top-k

Find Median from Data Stream

Problem (yeniden ifade)

Büyüyen bir akış üzerinde addNum(num) ve findMedian() destekle. Medyan ortadaki (tek) veya iki ortanın ortalaması (çift).

Sezgi

Alt yarıyı max-heap’te, üst yarıyı min-heap’te tut. Boyutları dengele: lo n/2 veya n/2+1 elemanlı olsun.

Yaklaşımlar

İki heap (max + min)

Tested only

Time O(log n) add, O(1) medianSpace O(n)

Fikir. Değere göre lo veya hi’ya it; lo.Count ≥ hi.Count ve |lo-hi| ≤ 1 olacak şekilde yeniden dengele. Medyan peek’lerden.

Adım adım. add 1,2,3 → lo=[2,1] hi=[3] → medyan 2; add 4 → 2 ve 3’ün ortalaması = 2.5.

Trade-off’lar. Sıralı liste O(n) ekleme; çift heap mülakat hedefidir.

Solution

export class MedianFinder {
  private lo: number[] = []; // max-heap (negated via sort desc)
  private hi: number[] = []; // min-heap

  addNum(num: number): void {
    if (this.lo.length === 0 || num <= this.lo[0]!) {
      this.lo.push(num);
      this.lo.sort((a, b) => b - a);
    } else {
      this.hi.push(num);
      this.hi.sort((a, b) => a - b);
    }
    if (this.lo.length > this.hi.length + 1) {
      this.hi.push(this.lo.shift()!);
      this.hi.sort((a, b) => a - b);
    } else if (this.hi.length > this.lo.length) {
      this.lo.push(this.hi.shift()!);
      this.lo.sort((a, b) => b - a);
    }
  }

  findMedian(): number {
    if (this.lo.length > this.hi.length) return this.lo[0]!;
    return (this.lo[0]! + this.hi[0]!) / 2;
  }
}

export class MedianFinder {
  private lo: number[] = []; // max-heap (negated via sort desc)
  private hi: number[] = []; // min-heap

  addNum(num: number): void {
    if (this.lo.length === 0 || num <= this.lo[0]!) {
      this.lo.push(num);
      this.lo.sort((a, b) => b - a);
    } else {
      this.hi.push(num);
      this.hi.sort((a, b) => a - b);
    }
    if (this.lo.length > this.hi.length + 1) {
      this.hi.push(this.lo.shift()!);
      this.hi.sort((a, b) => a - b);
    } else if (this.hi.length > this.lo.length) {
      this.lo.push(this.hi.shift()!);
      this.lo.sort((a, b) => b - a);
    }
  }

  findMedian(): number {
    if (this.lo.length > this.hi.length) return this.lo[0]!;
    return (this.lo[0]! + this.hi[0]!) / 2;
  }
}

Şablon bağlantısı

İki öncelik kuyruğu ile heap top-k / sıra istatistikleri.

Derinlemesine

İki heap alt yarıyı (max-heap) ve üst yarıyı (min-heap) boyuta göre dengede tutar. Değişmez: alttaki her değer üsttekilerden ≤, boyutlar en fazla 1 fark eder. Medyan altın max’ı (tek sayı) veya iki kökün ortalamasıdır (çift). Her eklemeden sonra yeniden dengele. Bu çevrimiçidir: tüm akışı yeniden sıralamazsın.

Sıralı liste tabanı

Tested only

Time O(n) per insertSpace O(n)

Fikir. Sayıları sıralı tut; ikili arama ile ekle; medyan ortada.

Trade-off’lar. Basit ve doğru; iki-heap sürümü mülakat için O(log n) ekleme.

Solution

/** Naive median: keep a sorted array (O(n) insert). */
export class MedianFinderSorted {
  private a: number[] = [];
  addNum(num: number): void {
    let lo = 0, hi = this.a.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.a[mid]! < num) lo = mid + 1;
      else hi = mid;
    }
    this.a.splice(lo, 0, num);
  }
  findMedian(): number {
    const n = this.a.length;
    const m = n >> 1;
    return n % 2 ? this.a[m]! : (this.a[m - 1]! + this.a[m]!) / 2;
  }
}

/** Naive median: keep a sorted array (O(n) insert). */
export class MedianFinderSorted {
  private a: number[] = [];
  addNum(num: number): void {
    let lo = 0, hi = this.a.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.a[mid]! < num) lo = mid + 1;
      else hi = mid;
    }
    this.a.splice(lo, 0, num);
  }
  findMedian(): number {
    const n = this.a.length;
    const m = n >> 1;
    return n % 2 ? this.a[m]! : (this.a[m - 1]! + this.a[m]!) / 2;
  }
}

Yansıma

Hangi kalıp bunu 90 saniyede ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozardı?