计算两个数组的交集

问题

给定两个数组，需要找出这两个数组中共同存在的元素，即计算它们的交集。例如，数组 [1, 2, 2, 1] 和 [2, 2] 的交集是 [2] 或 [2, 2]（取决于是否需要保留重复元素）。

需要考虑两种情况：

1. 交集中每个元素只出现一次（去重）
2. 交集中保留重复元素（根据元素在两个数组中出现的最小次数）

解答

/**
 * 方法一：使用 Set 求交集（去重版本）
 * @param {Array} arr1 - 第一个数组
 * @param {Array} arr2 - 第二个数组
 * @returns {Array} 交集数组（去重）
 */
function intersection(arr1, arr2) {
  const set1 = new Set(arr1);
  const set2 = new Set(arr2);
  return [...set1].filter(item => set2.has(item));
}

/**
 * 方法二：使用 Map 求交集（保留重复元素）
 * @param {Array} arr1 - 第一个数组
 * @param {Array} arr2 - 第二个数组
 * @returns {Array} 交集数组（保留重复）
 */
function intersect(arr1, arr2) {
  const map = new Map();
  const result = [];
  
  // 统计 arr1 中每个元素出现的次数
  for (const num of arr1) {
    map.set(num, (map.get(num) || 0) + 1);
  }
  
  // 遍历 arr2，如果元素在 map 中存在且次数大于 0，则加入结果
  for (const num of arr2) {
    if (map.get(num) > 0) {
      result.push(num);
      map.set(num, map.get(num) - 1);
    }
  }
  
  return result;
}

/**
 * 方法三：先排序再使用双指针（保留重复元素）
 * @param {Array} arr1 - 第一个数组
 * @param {Array} arr2 - 第二个数组
 * @returns {Array} 交集数组（保留重复）
 */
function intersectWithSort(arr1, arr2) {
  // 先对两个数组排序
  arr1.sort((a, b) => a - b);
  arr2.sort((a, b) => a - b);
  
  const result = [];
  let i = 0, j = 0;
  
  // 使用双指针遍历
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] === arr2[j]) {
      result.push(arr1[i]);
      i++;
      j++;
    } else if (arr1[i] < arr2[j]) {
      i++;
    } else {
      j++;
    }
  }
  
  return result;
}

使用示例

// 示例 1：去重版本
const arr1 = [1, 2, 2, 1];
const arr2 = [2, 2];
console.log(intersection(arr1, arr2)); // 输出: [2]

const arr3 = [4, 9, 5];
const arr4 = [9, 4, 9, 8, 4];
console.log(intersection(arr3, arr4)); // 输出: [4, 9]

// 示例 2：保留重复元素版本
console.log(intersect(arr1, arr2)); // 输出: [2, 2]
console.log(intersect([1, 2, 2, 1], [2])); // 输出: [2]

// 示例 3：使用排序双指针方法
console.log(intersectWithSort([1, 2, 2, 1], [2, 2])); // 输出: [2, 2]
console.log(intersectWithSort([4, 9, 5], [9, 4, 9, 8, 4])); // 输出: [4, 9]

// 示例 4：空数组情况
console.log(intersection([], [1, 2, 3])); // 输出: []
console.log(intersect([1, 2], [])); // 输出: []

// 示例 5：无交集情况
console.log(intersection([1, 2, 3], [4, 5, 6])); // 输出: []

关键点

• 方法选择：根据需求选择合适的方法

  • 需要去重：使用 Set 方法（方法一）
  • 保留重复：使用 Map 或双指针方法（方法二、三）

• 时间复杂度：

  • Set 方法：O(m + n)，其中 m 和 n 分别是两个数组的长度
  • Map 方法：O(m + n)
  • 排序双指针：O(m log m + n log n)，排序的时间复杂度

• 空间复杂度：

  • Set 方法：O(m)，需要存储第一个数组的所有元素
  • Map 方法：O(min(m, n))，最多存储较小数组的元素
  • 排序双指针：O(1)，不考虑排序的额外空间

• 边界情况处理：

  • 空数组的情况
  • 无交集的情况
  • 数组中包含重复元素的情况

• 性能优化：

  • 可以先判断哪个数组更小，用较小的数组构建 Set 或 Map
  • 对于已排序数组，直接使用双指针方法效率更高