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

Mediumquick-select

Kth Smallest Element in a Sorted Matrix

Problem (yeniden ifade)

Her satırı ve sütunu artan sıralı n × n matris. k. en küçük değeri döndür (1-tabanlı). Tekrarlar ayrı sayılır.

Sezgi

Düzleştirip quick-select sıralı yapıyı çöpe atar. Daha iyisi: n satır başının min-heap’i, k kez pop (her pop o satırdaki sonrakini iter). Veya değer aralığında ikili arama: sağ üstten yürüyerek ≤ mid kaç tane say.

Yaklaşımlar

Satır başlarının min-heap'i

Doğrulanmadı

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

Fikir. Her satır için (matrix[r][0], r, 0) it. Global min’i k kez çek; (v, r, c) çektikten sonra varsa (matrix[r][c+1], r, c+1) it. k. pop cevap.

Yürüyüş. [[1,5,9],[10,11,13],[12,13,15]], k=8. Sekiz pop sonra 13.

Trade-off. Satır-sıralı özelliği kullanır. k = n² olabilir, en kötü O(n² log n). Düz kopyada quick select ortalama O(n²) ve sütunları yok sayar.

Çözüm

/** Toy min-heap: sort + shift. Interview/production: binary heap. */
export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const pq: [number, number, number][] = [];
  for (let r = 0; r < n; r++) pq.push([matrix[r]![0]!, r, 0]);
  let v = 0;
  for (let t = 0; t < k; t++) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const cur = pq.shift()!;
    v = cur[0]!;
    const r = cur[1]!, c = cur[2]!;
    if (c + 1 < n) pq.push([matrix[r]![c + 1]!, r, c + 1]);
  }
  return v;
}

/** Toy min-heap: sort + shift. Interview/production: binary heap. */
export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const pq: [number, number, number][] = [];
  for (let r = 0; r < n; r++) pq.push([matrix[r]![0]!, r, 0]);
  let v = 0;
  for (let t = 0; t < k; t++) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const cur = pq.shift()!;
    v = cur[0]!;
    const r = cur[1]!, c = cur[2]!;
    if (c + 1 < n) pq.push([matrix[r]![c + 1]!, r, c + 1]);
  }
  return v;
}

Değer üzerinde ikili arama

Doğrulanmadı

Zaman O(n log n log Δ)Alan O(1)

Fikir. lo = matrix[0][0], hi = matrix[n-1][n-1]. ≤ mid sayımı O(n): her satıra sağdan başla, sola yürü. Sayı < k ise sağa, değilse sola. lo k. değere yakınsar.

Yürüyüş. Aynı matris, k=8. [1,15] içinde en az 8 girdi ≤ olan en küçük aday 13.

Trade-off. Heap yok. Sayım O(n) olmalı, O(n²) değil. Binary-search-on-answer’ın sıra istatistiğine uygulanışı.

Çözüm

export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const countLe = (x: number): number => {
    let c = 0, j = n - 1;
    for (let i = 0; i < n; i++) {
      while (j >= 0 && matrix[i]![j]! > x) j--;
      c += j + 1;
    }
    return c;
  };
  let lo = matrix[0]![0]!, hi = matrix[n - 1]![n - 1]!;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (countLe(mid) < k) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

export function kthSmallest(matrix: number[][], k: number): number {
  const n = matrix.length;
  const countLe = (x: number): number => {
    let c = 0, j = n - 1;
    for (let i = 0; i < n; i++) {
      while (j >= 0 && matrix[i]![j]! > x) j--;
      c += j + 1;
    }
    return c;
  };
  let lo = matrix[0]![0]!, hi = matrix[n - 1]![n - 1]!;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (countLe(mid) < k) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

Şablon bağlantısı

Yapılı kaynakta kth-smallest seçimi. Heap / ikili arama, düzleştirme + quick select’i yener çünkü satır ve sütunlar sıralı.

Yansıma

Heap: her satırın başı yığında. Pop edilenin sağını it. k’ıncı pop cevap.
İkili arama değerde. ≤ mid sayımı satırlar sıralı diye O(n). Sayı k’dan küçükse sağa.
k = 1 en küçük, k = n² en büyük. Yinelenenler ayrı sayılır. Negatif eşik aramayı bozmaz.