หาส่วนร่วมของสองอาร์เรย์ (Intersection) - JavaScript

หาเอลีเมนต์ที่ปรากฏในทั้งสองอาร์เรย์ (Intersection) นับความถี่ตามที่น้อยกว่า (Multiset Intersection)

ตัวอย่าง

arr1 = ['hello', 'world', 'how', 'are', 'you']
arr2 = ['hey', 'world', 'can', 'you', 'rotate']
Intersection: ['world', 'you']

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

const intersectElements = (arr1, arr2) => {
  const res = [];
  const smaller = arr1.length < arr2.length ? arr1 : arr2;
  const bigger = arr1.length >= arr2.length ? arr1 : arr2;
  const biggerCopy = [...bigger];
  
  for (const item of smaller) {
    const idx = biggerCopy.indexOf(item);
    if (idx !== -1) {
      res.push(item);
      biggerCopy[idx] = undefined; // Mark as used
    }
  }
  return res;
};

ผลลัพธ์

[ 'world', 'you' ]

วิธีแบบ Map (O(n+m) - เร็วกว่า)

const intersectElements = (arr1, arr2) => {
  const freq = new Map();
  for (const v of arr1) freq.set(v, (freq.get(v) || 0) + 1);
  
  const res = [];
  for (const v of arr2) {
    if ((freq.get(v) || 0) > 0) {
      res.push(v);
      freq.set(v, freq.get(v) - 1);
    }
  }
  return res;
};

Unique Intersection (Set)

const uniqueIntersection = (a, b) => [...new Set(a)].filter(x => new Set(b).has(x));