两个数组的交集 JavaScript

javascriptweb developmentobject oriented programming更新于 2025/10/8 23:08:17

我们有两个数字数组，我们需要编写一个函数，例如intersection()，它计算它们的交集并返回一个包含任何顺序的相交元素的数组。结果中的每个元素应出现的次数与它在两个数组中显示的次数相同。

例如 − 如果，

输入:arr1 = [1,2,3,1]，arr2 = [1,3,1]
输出:[1,3,1]

方法

如果数组已排序，我们可以使用两个指针方法，最初都指向 0 各自数组的开头，然后我们可以继续增加相应的指针，这将是 O(m+n) 复杂度。时间，其中 m 和 n 是数组的大小。

但由于我们的数组是未排序的，因此对数组进行排序没有任何逻辑，然后使用这种方法，我们将检查第一个值与第二个值的每个值，并构造一个交集数组。这将花费我们 O(n^2) 的时间。

执行此操作的代码将是 −

示例

const arr1 = [1, 2, 43, 5, 3, 7, 7,8, 4, 2];
const arr2 = [1, 1, 6, 6, 2, 78, 7, 2, 3, 7, 23, 5, 3];
const intersection = (arr1, arr2) => {
   const res = [];
   const { length: len1 } = arr1;
   const { length: len2 } = arr2;
   const smaller = (len1 < len2 ? arr1 : arr2).slice();
   const bigger = (len1 >= len2 ? arr1 : arr2).slice();
   for(let i = 0; i < smaller.length; i++){
      if(bigger.indexOf(smaller[i]) !== -1){
         res.push(smaller[i]);
         bigger.splice(bigger.indexOf(smaller[i]), 1, undefined);
      }
   };
   return res;
};
console.log(intersection(arr1 ,arr2));