差集

2023年06月19日

柏拉文

越努力，越幸运

一、认识

---

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

二、实现

---

2.1 Lodash

2.2 Bolawen Set

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

实现

function differenceImpl(set1, set2) {
  const differenceSet = new Set();
  for (let num of set1) {
    if (!set2.has(num)) {
      differenceSet.add(num);
    }
  }
  return [...differenceSet];
}

function difference(array1, array2) {
  const set1 = new Set(array1);
  const set2 = new Set(array2);
  return differenceImpl(set1, set2);
}

测试

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

function differenceImpl(set1, set2) {
  const differenceSet = new Set();
  for (let num of set1) {
    if (!set2.has(num)) {
      differenceSet.add(num);
    }
  }
  return [...differenceSet];
}

function difference(array1, array2) {
  const set1 = new Set(array1);
  const set2 = new Set(array2);
  return differenceImpl(set1, set2);
}

const result = difference(array1, array2);
console.log(result); // 输出 [1, 7, 9]

2.2 Boloawen filter includes

实现

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

测试

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

const result = difference(array1, array2);
console.log(result); // 输出 [1, 7, 9]