JavaScript查找二维数组跨子数组共有元素的高性能可扩展方案

核心思路 #

原有实现采用两两子数组遍历对比元素的方式，当子数组数量或子数组内元素数量较大时，嵌套循环会带来指数级的性能损耗，同时后续还要对结果做排序去重，额外增加了耗时。
优化后仅需线性遍历所有元素，统计每个数字出现过的不同子数组的数量（同一个子数组内的重复数字只计一次），最后统计有多少个数字的计数≥2即可，整体时间复杂度为所有元素总数量级，性能提升非常明显。

优化后代码 #

let t0 = performance.now();

let arr = [
  [1, 1, 5, 2, 3],
  [4, 5, 6, 4, 3],
  [9, 4, 4, 1, 5]
];

// 存储每个数字出现的不同子数组数量
const numAppearCount = new Map();

arr.forEach((subArr) => {
  // 先对当前子数组去重，避免同数组内重复元素多次计数
  const uniqueNums = new Set(subArr);
  uniqueNums.forEach((num) => {
    numAppearCount.set(num, (numAppearCount.get(num) || 0) + 1);
  });
});

// 筛选出现在至少2个不同子数组的数字
const result = [];
numAppearCount.forEach((count, num) => {
  if (count >= 2) {
    result.push(num);
  }
});

console.log(result); // 输出 [1,5,3,4]
console.log(result.length); // 输出 4

let t1 = performance.now();
console.log(`time taken ${t1 - t0} milliseconds.`);

方案优势 #

• 性能提升显著：如果有100个子数组，每个子数组平均100个元素，原有方案需要执行近5000万次操作，优化后仅需执行1万次操作，数据量越大性能优势越明显
• 可扩展性强：如果后续需求变更为统计至少出现在3个、N个不同子数组的元素，仅需修改判断条件count >= 2中的数值即可，无需调整整体逻辑
• 逻辑简洁：没有冗余的两两数组对比、结果排序去重步骤，可读性更高

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