【每日一题】查找两个数组的交集

题目：查找两个数组的交集

要求：

编写一个函数，接受两个数组作为参数，返回这两个数组的交集（包含在两个数组中的所有元素的集合，不考虑顺序）。要求时间复杂度尽量低。

function intersection(arr1, arr2) {  // 在这里实现查找交集的算法}
// 示例用法：const array1 = [1, 2, 2, 1];const array2 = [2, 2];
const result = intersection(array1, array2);console.log(result); // 应该输出 [2]

在回答中，可以考虑不同解决方案的优劣，并解释所选择算法的原理和实现思路。

方法一：使用 Set 数据结构

function intersection(arr1, arr2) {  const set1 = new Set(arr1);  const set2 = new Set(arr2);  return [...set1].filter(item => set2.has(item));}

原理和实现思路：

利用 Set 数据结构的唯一性，分别将两个数组转为 Set。

使用 filter 方法遍历第一个 Set，只保留在第二个 Set 中存在的元素。

最后将结果转为数组返回。

优势：

简洁、直观，利用 Set 的唯一性能够在 O(n) 时间内完成。

劣势：

需要额外的空间存储 Set 对象。

方法二：使用哈希表

function intersection(arr1, arr2) {  const map = {};  const result = [];
  for (const num of arr1) {    map[num] = (map[num] || 0) + 1;  }
  for (const num of arr2) {    if (map[num] > 0) {      result.push(num);      map[num]--;    }  }
  return result;}

原理和实现思路：

使用一个哈希表记录第一个数组中每个元素的出现次数。

遍历第二个数组，如果元素在哈希表中存在且出现次数大于零，则加入结果数组，同时减少哈希表中该元素的出现次数。

优势：

在一些情况下，可能比 Set 更灵活，适用于处理一些特定问题。

劣势：

需要额外的空间存储哈希表。

总结：

两种方法的时间复杂度均为 O(n)，其中 n 为较小的数组的长度。在实际应用中，可以根据具体情况选择不同的方法。如果空间复杂度要求较高，使用哈希表可能更为合适；如果追求简洁和直观，使用 Set 可以更容易理解和维护。

限 时 特 惠： 本站每日持续更新海量各大内部创业教程，一年会员只需98元，全站资源免费下载 点击查看详情
站 长 微 信： lzxmw777