一、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中的当前元素。如果当前元素相等,则将其加入到结果数组中,否则将指针偏移。