跳到主要内容

交集

2023年06月19日
柏拉文
越努力,越幸运

一、认识


有两数组 array1array2, 实现一个 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);