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

Find K Pairs with Smallest Sums

Problem (yeniden ifade)

İki artan sıralı dizi. nums1’den u, nums2’den v olacak şekilde en küçük toplamlı k çift (u,v) döndür.

Sezgi

i < k için (nums1[i], nums2[0]) ile başla. En küçük toplamı pop et; aynı i için sonraki j+1’i push et.

Yaklaşımlar

İlk sütun üzerinde min-heap

Doğrulanmadı

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

Fikir. Tam n×m matristen kaçın. Heap yalnızca en iyi satırlar için nums2 boyunca genişler.

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

Trade-off. Sıralı diziler şart; sıra yoksa çiftlerin tam sıralamasına düş.

Çözüm

export function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
  const res: number[][] = [];
  if (!nums1.length || !nums2.length || k <= 0) return res;
  // min-heap of [sum, i, j]
  const heap: [number, number, number][] = [];
  const push = (i: number, j: number) => {
    heap.push([nums1[i]! + nums2[j]!, i, j]);
    heap.sort((a, b) => a[0]! - b[0]!);
  };
  const n1 = Math.min(nums1.length, k);
  for (let i = 0; i < n1; i++) push(i, 0);
  while (k-- > 0 && heap.length) {
    const [, i, j] = heap.shift()!;
    res.push([nums1[i]!, nums2[j]!]);
    if (j + 1 < nums2.length) push(i, j + 1);
  }
  return res;
}

export function kSmallestPairs(nums1: number[], nums2: number[], k: number): number[][] {
  const res: number[][] = [];
  if (!nums1.length || !nums2.length || k <= 0) return res;
  // min-heap of [sum, i, j]
  const heap: [number, number, number][] = [];
  const push = (i: number, j: number) => {
    heap.push([nums1[i]! + nums2[j]!, i, j]);
    heap.sort((a, b) => a[0]! - b[0]!);
  };
  const n1 = Math.min(nums1.length, k);
  for (let i = 0; i < n1; i++) push(i, 0);
  while (k-- > 0 && heap.length) {
    const [, i, j] = heap.shift()!;
    res.push([nums1[i]!, nums2[j]!]);
    if (j + 1 < nums2.length) push(i, j + 1);
  }
  return res;
}

Şablon bağlantısı

Sıralı çarpım uzayında heap BFS (k-yönlü tarz).

Yansıma

İlk sütun: her nums1[i] + nums2[0]. Pop edilenin sağ komşusu j+1 itilir.
Aynı çifti iki kez itmemek için ya visited ya da “yalnızca j artar” şekli.
k tüm çiftlerden büyükse hepsi. Bir dizi boşsa cevap boş.