您的位置:

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