JavaScript嵌套数组重复值检测的效率分析与优化问询

原函数的性能瓶颈分析 #

先拆解你当前deepSort函数的执行流程和对应的时间复杂度：

1. nestedArray.flat()：扁平化嵌套数组，时间复杂度O(n)（n为所有元素的总个数）。
2. .sort()：对扁平化后的数组排序，JavaScript内置排序采用Timsort算法，时间复杂度O(n log n)。
3. 遍历排序数组收集重复项：时间复杂度O(n)。
4. results.filter(...)：通过indexOf去重，每次indexOf都是线性查找，这一步的时间复杂度是O(k²)（k为重复项数组的长度，最坏情况k接近n）。

整体时间复杂度为O(n log n + k²)，当处理超大数据量时，排序操作和最后的去重步骤会成为明显的性能瓶颈——排序的O(n log n)开销会随数据量激增而快速上升，而filter里的重复线性查找更是会让性能急剧下降。

优化方案：基于哈希表的统计法 #

核心思路是用哈希表（推荐用Map，支持所有类型的键，比普通对象更可靠）一次性统计每个元素的出现次数，再筛选出出现次数>1的元素。这种方法不需要排序，时间复杂度可降至O(n)，空间复杂度仅取决于唯一元素的数量，在超大数据量场景下性能提升显著。

通用嵌套场景优化代码 #

function findDuplicates(nestedArray) {
  const countMap = new Map();
  
  // 递归遍历嵌套数组统计元素出现次数
  const traverse = (arr) => {
    for (const item of arr) {
      Array.isArray(item) ? traverse(item) : countMap.set(item, (countMap.get(item) || 0) + 1);
    }
  };
  traverse(nestedArray);
  
  // 收集出现次数大于1的元素
  const duplicates = [];
  countMap.forEach((count, num) => {
    if (count > 1) duplicates.push(num);
  });
  
  return duplicates.join();
}

// 测试用例
const a = findDuplicates([[1,3,4,5], [4,7,9,1,3], [2,3,5], [1,2,3,4]]) // 返回 "1,2,3,4,5"
console.log(a);

const b = findDuplicates([[1,2,3], [4,5], [6,7,8], [2,9,0]]) // 返回 "2"
console.log(b);

const c = findDuplicates([[2,7,9], [4,3], [9,6,5], [1,4,3]]) // 返回 "3,4,9"
console.log(c);

单层嵌套场景简化代码 #

如果确定输入的嵌套数组只有一层深度（比如示例中的结构），可以省略递归，直接用flat()扁平化后遍历：

function findDuplicates(nestedArray) {
  const countMap = new Map();
  for (const num of nestedArray.flat()) {
    countMap.set(num, (countMap.get(num) || 0) + 1);
  }
  return Array.from(countMap)
    .filter(([_, count]) => count > 1)
    .map(([num]) => num)
    .join();
}

性能对比 #

• 原方案：数据量达到10万级以上时，排序和去重步骤会明显卡顿，尤其是重复元素较多时，filter的O(k²)开销会让运行时间大幅增加。
• 优化方案：无论数据量多大，都保持线性时间复杂度，内存开销仅取决于唯一元素的数量，在超大数据量场景下性能提升非常显著。

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