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

Kth Largest Element in an Array

Problem (yeniden ifade)

Sıralanmamış bir dizide k. en büyük elemanı bul (benzersiz olma şartı yok).

Sezgi

Boyu k min-heap görülen en büyük k’yı tutar; kök k. en büyük. Quick select, pivot n-k indeksine oturana dek partition eder.

Yaklaşımlar

Boyu k min-heap

Doğrulanmadı

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

Fikir. Hepsini push et; size>k olunca pop; peek döndür.

Yürüyüş. [3,2,1,5,6,4], k=2 → 5.

Trade-off. Heap O(n log k) vs quickselect ortalama O(n). k çok küçükse veya dizi bozulmamalıysa heap tercih et.

Çözüm

export function findKthLargest(nums: number[], k: number): number {
  // min-heap via sorted insert on small k (simple, correct)
  const heap: number[] = [];
  const push = (x: number) => {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  };
  for (const x of nums) push(x);
  return heap[0]!;
}

export function findKthLargest(nums: number[], k: number): number {
  // min-heap via sorted insert on small k (simple, correct)
  const heap: number[] = [];
  const push = (x: number) => {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  };
  for (const x of nums) push(x);
  return heap[0]!;
}

Quick select

Doğrulanmadı

Zaman O(n) averageAlan O(1)

Fikir. k. en büyük, sıralı düzende n-k indeksindeki elemandır. Pivot oraya oturana dek rastgele partition; yalnızca bir tarafa ilerle. Diziyi yerinde değiştirir.

Yürüyüş. [3,2,1,5,6,4], k=2 → hedef indeks 4. Partition’lardan sonra 4. indeksteki değer 5.

Trade-off. Ortalama O(n), rastgele pivot yoksa en kötü O(n²). Quick Select varsayılanı. k 1-indeksli.

Çözüm

export function findKthLargest(nums: number[], k: number): number {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

export function findKthLargest(nums: number[], k: number): number {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

Şablon bağlantısı

Heap top-K, veya n-k sırası için Quick Select. Her iki pattern için amiral gemisi k. en büyük problemi.

Yansıma

k boyutlu min-heap’in tepesi k’ıncı büyük. n’i itip k’dan büyükse pop. Quickselect ortalama O(n).
k == n en küçük, k == 1 en büyük. Yinelenenler ayrı eleman sayılır; tekilleştirme yok.
Kötü pivot quickselect’i O(n²) yapar. Heap O(n log k) garanti.