交集

2023年06月19日

柏拉文

越努力，越幸运

一、认识

---

有两数组 array1 和 array2, 实现一个 intersection 函数，使得可以找出 array1 有且 array2 也有的元素，组成一个新的数组。

二、实现

---

2.1 Lodash

2.2 Bolawen Set

思路: 使用哈希集合存储元素，则可以在 O(1) 的时间内判断一个元素是否在集合中，从而降低时间复杂度。首先使用两个集合分别存储两个数组中的元素，然后遍历较小的集合，判断其中的每个元素是否在另一个集合中，如果元素也在另一个集合中，则将该元素添加到返回值。该方法的时间复杂度可以降低到 O(m+n)。

实现

function intersectionImpl(set1, set2) {
  if (set1.size > set2.size) {
    return intersectionImpl(set2, set1);
  }
  const intersection = new Set();
  for (let num of set1) {
    if (set2.has(num)) {
      intersection.add(num);
    }
  }
  return [...intersection];
}
function intersection(array1, array2) {
  const set1 = new Set(array1);
  const set2 = new Set(array2);
  return intersectionImpl(set1, set2);
}

测试

const array1 = [1, 3, 5, 7, 9];
const array2 = [3, 4, 5];

const result = intersection(array1, array2);
console.log(result); 

2.2 Bolawen filter includes

实现

function intersection(array1, array2) {
    return array1.filter(item => array2.includes(item));
}

测试

const array1 = [1, 3, 5, 7, 9];
const array2 = [3, 4, 5];

const result = intersection(array1, array2);
console.log(result);