JavaScript實現兩個數組取交集

一、js兩個數組取交集的差級

在JavaScript中，可以使用Set對象實現兩個數組的差集。Set是一種特殊的數據結構，它是一組獨特且不重複的值的集合。

const set1 = new Set([1, 2, 3, 4, 5]);
const set2 = new Set([4, 5, 6, 7, 8]);
const difference = new Set(Array.from(set1).filter(x => !set2.has(x)));
console.log(difference); // Set {1, 2, 3}

這裡通過Set對象來存儲兩個數組的值，然後根據判斷條件，得到差級。這裡使用了Array.from()方法將Set對象轉換為數組，使用filter()方法過濾出符合條件的結果。

二、js兩個數組取交集演算法

JavaScript中，還可以使用更簡單的方法來實現兩個數組的交集。對於數組1進行遍歷，比較數組2中的每個元素，如果找到相等的則加入到結果數組中。不過需要注意的是，在對於數組的遍歷過程中，需要使用indexOf()函數來進行判斷該元素是否存在於數組2中。

const arr1 = [1, 2, 3, 4, 5];
const arr2 = [4, 5, 6, 7, 8];
const intersection = [];
for (let i = 0; i < arr1.length; i++) {
  if (arr2.indexOf(arr1[i]) !== -1) {
    intersection.push(arr1[i]);
  }
}
console.log(intersection); // [4, 5]

上述方法的時間複雜度為O(n^2)，如果兩個數組的長度特別大，那麼執行效率可能會非常低。為了避免這種情況，可以使用更高效的演算法。

三、js兩個數組的交集

對於兩個數組的交集問題，可以採用哈希表（HashMap）來實現。將其中一個數組的元素存儲在哈希表中，然後遍歷另一個數組，判斷該數組的元素是否在哈希表中存在。

function intersection(arr1, arr2) {
  const map = new Map();
  const result = [];
  for (let i = 0; i < arr1.length; i++) {
    map.set(arr1[i], true);
  }
  for (let j = 0; j < arr2.length; j++) {
    if (map.get(arr2[j])) {
      result.push(arr2[j]);
    }
  }
  return result;
}
console.log(intersection([1, 2, 3, 4, 5], [4, 5, 6, 7, 8])); // [4, 5]

使用Map對象將數組1中的元素存入，然後判斷數組2中的元素是否在Map中出現過，並將其加入到結果數組中。

四、js兩個數組取差集

除了求交集，還有一個常用的問題就是求差級。可以使用數組中的filter()方法來實現。

function difference(arr1, arr2) {
  return arr1.filter(x => !arr2.includes(x));
}
console.log(difference([1, 2, 3, 4, 5], [4, 5, 6, 7, 8])); // [1, 2, 3]

該方法中，使用filter()方法過濾掉數組1中在數組2中出現過的元素。

五、計算兩個數組的交集

以上介紹的演算法都是基於無序數組計算交集的。對於有序數組，可以採用更高效的方法來計算交集。這裡可以使用雙指針技巧。

function intersection(arr1, arr2) {
  const result = [];
  let i = 0, j = 0;
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      i++;
    } else if (arr1[i] > arr2[j]) {
      j++;
    } else {
      result.push(arr1[i]);
      i++;
      j++;
    }
  }
  return result;
}
console.log(intersection([1, 2, 3, 4, 5], [4, 5, 6, 7, 8])); // [4, 5]

該方法使用了i和j兩個指針，分別指向數組1和數組2中的當前元素。如果當前元素相等，則將其加入到結果數組中，否則將指針偏移。