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

Mediumheap-top-k quick-select

K Closest Points to Origin

Problem (yeniden ifade)

Düzlemde noktalar ve tamsayı k verildiğinde, (0,0)’a en yakın k noktayı döndür. Cevaplar arasındaki sıra değişebilir.

Sezgi

En yakın k’yı kare uzaklıkla anahtarlanmış bir max-heap ile tut (sqrt’ten kaçın).

Yaklaşımlar

Boyu k max-heap

Doğrulanmadı

Zaman O(n log k)Alan O(k)

Fikir. Her noktayı push et; heap boyu > k ise en uzağı pop et. Kalan heap cevap çoklu kümesidir.

Yürüyüş. [[1,3],[-2,2]], k=1 → [[-2,2]].

Trade-off. Tam sıralama O(n log n); heap k ≪ n iken kazanır. Quickselect ortalama O(n).

Çözüm

export function kClosest(points: number[][], k: number): number[][] {
  // max-heap of size k by distance
  const heap: number[][] = [];
  const dist = (p: number[]) => p[0]! * p[0]! + p[1]! * p[1]!;
  for (const p of points) {
    heap.push(p);
    heap.sort((a, b) => dist(b) - dist(a));
    if (heap.length > k) heap.shift();
  }
  return heap;
}

export function kClosest(points: number[][], k: number): number[][] {
  // max-heap of size k by distance
  const heap: number[][] = [];
  const dist = (p: number[]) => p[0]! * p[0]! + p[1]! * p[1]!;
  for (const p of points) {
    heap.push(p);
    heap.sort((a, b) => dist(b) - dist(a));
    if (heap.length > k) heap.shift();
  }
  return heap;
}

Şablon bağlantısı

Sınırlı max-heap ile klasik top-k.

Yansıma

Uzaklık karesi yeter; sqrt sırayı değiştirmez. k boyutlu max-heap en uzağı atar.
Eşit uzaklıkta hangisinin kaldığı serbest. k == n hepsi, k == 1 en yakın.
(0,0) uzaklık 0. Negatif koordinat karede işaretini kaybeder.