การหาคู่ตัวเลขจาก 2 อาร์เรย์ที่มีผลรวมน้อยที่สุด k คู่ใน JavaScript

ปัญหา

กำหนด 2 sorted arrays arr1, arr2 หา k คู่ (arr1[i], arr2[j]) ที่มีผลรวมน้อยที่สุด

ตัวอย่าง

arr1 = [1,1,2], arr2 = [1,2,3], k = 2
output: [[1,1], [1,1]]

ตัวอย่างโค้ด

const arr1 = [1, 1, 2];
const arr2 = [1, 2, 3];
const num = 2;

const smallestPairs = (arr1 = [], arr2 = [], num = 1) => {
  const temp = Array(arr1.length).fill(0);
  const res = [];
  let compute = () => {
    let flag = Infinity;
    for (let i = 0; i < arr1.length; i++) {
      if (temp[i] < arr2.length && flag > (arr1[i] + arr2[temp[i]])) {
        flag = arr1[i] + arr2[temp[i]];
      }
    }
    if (flag === Infinity || res.length >= num) {
      return;
    } else {
      for (let i = 0; i < arr1.length; i++) {
        if (temp[i] < arr2.length && flag == (arr1[i] + arr2[temp[i]])) {
          res.push(Array.of(arr1[i], arr2[temp[i]]));
          temp[i]++;
        }
      }
      compute();
    }
  };
  compute();
  return res.slice(0, num);
};

console.log(smallestPairs(arr1, arr2, num));

ผลลัพธ์

[[1, 1], [1, 1]]

คำอธิบาย

ใช้ array temp เก็บ index ของ arr2 ที่จับคู่กับ arr1[i] ปัจจุบัน

หา minimum sum ปัจจุบัน (flag) จากทุกคู่ที่เป็นไปได้ (temp[i] < arr2.length)

เพิ่มคู่ที่มี sum = flag ทั้งหมด แล้ว recursive หาคู่ถัดไป

Time: O(k * m) m = arr1.length, ไม่ได้ใช้ heap ที่มีประสิทธิภาพ O(k log m)