JavaScript如何实现按出现次数匹配的有序两数组交集

原有实现的问题 #

当前写法是纯集合成员判断的交集实现，仅校验元素是否存在于第二个数组中，没有对重复元素的匹配次数做限制：

function arraysCommon(array1, array2) {
  return array1.filter(x => array2.includes(x));
}

该实现的测试表现不符合预期：

• 测试入参：array1 = [1,2,3,2,1]、array2 = [5,4,3,2,1]
• 错误返回结果：[1,2,3,2,1]
• 预期返回结果：[1,2,3]（顺序与第一个数组中元素出现顺序一致）

注：第二个数组中1、2、3三个元素各仅出现1次，数组内的重复元素需要作为独立实体处理。

目标功能规则 #

需要实现的是多重集（元素可重复，重复项视为独立个体）的交集计算，需同时满足以下要求：

• 第一个数组中的每个元素最多只能匹配第二个数组中的一个元素
• 两个数组中的重复元素均视为独立实体，按出现次数对应匹配，最终取同元素在两个数组中出现次数的最小值
• 返回结果的元素顺序完全由第一个数组的元素顺序决定

实现思路 #

不需要复杂的双重循环对比，通过哈希表统计第二个数组的元素剩余可匹配次数即可实现，整体时间复杂度为O(n+m)：

1. 先遍历第二个数组，用Map记录每个元素的剩余可匹配次数
2. 再遍历第一个数组，对当前遍历到的元素做判断：
   • 如果该元素在计数表中的剩余次数大于0，就将该元素加入结果数组，同时把计数表中对应剩余次数减1
   • 如果剩余次数为0或者计数表中不存在该元素，直接跳过
3. 遍历完成后返回的结果数组即符合要求

参考实现代码 #

function arraysCommon(array1, array2) {
  // 统计array2中各元素的可匹配次数
  const countMap = new Map();
  for (const item of array2) {
    countMap.set(item, (countMap.get(item) || 0) + 1);
  }

  const result = [];
  for (const item of array1) {
    const remainCount = countMap.get(item);
    if (remainCount > 0) {
      result.push(item);
      // 匹配成功后剩余可匹配次数减1
      countMap.set(item, remainCount - 1);
    }
  }
  return result;
}

代码验证：传入[1,2,3,2,1]和[5,4,3,2,1]时，返回结果为[1,2,3]，符合预期；传入[1,2,2,3]和[2,2,2,4]时，返回结果为[2,2]，符合重复元素按次数匹配的规则。

逻辑差异说明 #

两种交集逻辑的差异可参考下图：

内容的提问来源于stack exchange，提问作者FreeAntiVirus