สมาชิกร่วมที่มีผลรวมดัชนีน้อยที่สุดใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับสองอาร์เรย์ของลิเทอรัล arr1 และ arr2 เป็นอาร์กิวเมนต์แรกและสอง ฟังก์ชันควรหาสมาชิกร่วม (common element) ใน arr1 และ arr2 ที่มีผลรวมดัชนี (index sum) น้อยที่สุด หากมี tie ให้คืนค่าทั้งหมด ไม่จำเป็นต้องเรียง

เช่น ถ้าอินพุตคือ:

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['d', 'a', 'c'];

ผลลัพธ์ควรเป็น:

const output = ['a'];

คำอธิบายผลลัพธ์

เพราะ 'd' และ 'a' ร่วมกันในทั้งสองอาร์เรย์ index sum ของ 'd' คือ 3+0=3 และของ 'a' คือ 0+1=1 ดังนั้น 'a' คือสมาชิกที่ต้องการ

ตัวอย่าง

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

const arr1 = ['a', 'b', 'c', 'd'];
const arr2 = ['d', 'a', 'c'];
const findCommon = (arr1 = [], arr2 = []) => {
  let sum = Infinity;
  const map = arr1.reduce((acc, str, index) => {
    acc[str] = index;
    return acc;
  }, {});
  for (let i = 0; i < arr2.length; i++) {
    const index1 = map[arr2[i]];
    if (index1 >= 0 && index1 + i < sum) {
      sum = index1 + i;
    }
  }
  const result = [];
  for (let i = 0; i < arr2.length; i++) {
    const index1 = map[arr2[i]];
    if (index1 >= 0 && index1 + i === sum) {
      result.push(arr2[i]);
    }
  }
  return result;
};
console.log(findCommon(arr1, arr2));

ผลลัพธ์

['a']

คำอธิบายเพิ่มเติม

สร้าง map จาก arr1: element→index หา min index sum โดยวน arr2 แล้วเก็บเฉพาะที่ sum เท่ากับ min O(n+m) time, O(n) space