数组指定频次元素筛选算法优化及时间复杂度判定

需求与现有实现 #

需求为实现接收两个序列参数A、B和计数参数p的函数，返回结果序列C：C需保留A中所有元素的原有顺序，剔除所有在序列B中恰好出现p次的元素。
参考示例：

输入：
A = [2,3,9,2,5,1,3,7,10]
B = [2,1,3,4,3,10,6,6,1,7,10,10,10]
p = 2
输出：C = [2,9,2,5,7,10]

你当前编写的实现代码如下：

function cSequence(a, b, p) {
  const times = {};
  b.forEach((item) => {
    if (times[item]) {
      times[item] += 1;
    } else {
      times[item] = 1;
    }
  });
  const pTimes = b.filter((item) => (times[item] == p ? true : false));
  return a.filter((item) => !pTimes.includes(item));
}

问题1：当前实现的时间复杂度判定 #

首先明确大O复杂度标记规则：大O只保留最高阶项，忽略所有常数系数，从来没有O(3n)这种标准记法，只要是和数据规模成线性正比的操作，无论遍历2次、3次还是10次，都记为O(n)。
但要注意：你当前的实现实际时间复杂度远高于线性，属于O(n*m)级别，问题出在最后一步的Array.includes()：

• includes方法每次执行都会线性遍历pTimes数组做匹配，假设A的长度为n，pTimes的长度为m，这一步最坏情况要做n*m次比较
• 如果B中大部分元素都恰好出现p次，m的长度和B的长度是同一量级，整体复杂度会退化到O((len(A)+len(B))²)的平方级
  你之前误以为是3次线性遍历，是漏算了includes自带的隐式循环开销。

问题2：更优的实现方案 #

最优实现可以做到真正的线性时间复杂度O(len(A) + len(B))，核心思路是去掉冗余的pTimes数组和低效的includes查找，直接用之前统计好的频次哈希表做O(1)时间的判断。
优化后代码：

function cSequence(a, b, p) {
  const countMap = new Map();
  // 遍历B统计每个元素出现次数
  for (const item of b) {
    countMap.set(item, (countMap.get(item) || 0) + 1);
  }
  // 遍历A直接过滤，查Map的时间是O(1)
  return a.filter(item => countMap.get(item) !== p);
}

优化点说明：

• 去掉了遍历B生成pTimes数组的冗余步骤，省了一次线性遍历和对应的内存占用
• 把includes的线性查找替换为哈希表O(1)查找，彻底消除平方级复杂度的隐患
• 用Map替代普通对象做频次统计，避免普通对象键的隐式类型转换问题（比如数字1和字符串'1'被识别为同一个键的bug）

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