如何使用Map/Set将代码优化至O(n)时间复杂度？

原代码的问题在于每次遍历排除规则都要重新过滤整个items数组，时间复杂度为O(m*n)（m是排除规则数量，n是items数量）。优化思路是先把排除规则预处理成键值对应的集合结构，然后只遍历一次items数组完成过滤，整体时间复杂度变为O(n+m)，属于O(n)级别。

实现代码 #

let items = [
  {type: 'a', name: 'a1', color: 'yellow'},
  {type: 'b', name: 'b1', color: 'orange'}
];
const excludes = [
  {k: 'color', value: 'yellow'},
  {k: 'name', value: 'x'}
];

// 预处理排除规则：按键分组存储要排除的值
const excludeMap = new Map();
excludes.forEach(({k, value}) => {
  if (!excludeMap.has(k)) {
    excludeMap.set(k, new Set());
  }
  excludeMap.get(k).add(value);
});

// 一次遍历完成过滤
const filteredItems = items.filter(item => {
  // 检查item的每个键是否在排除规则中，且对应值在排除集合里
  for (const [key, excludeValues] of excludeMap) {
    if (excludeValues.has(item[key])) {
      return false;
    }
  }
  return true;
});

console.log(filteredItems);

思路说明 #

1. 预处理排除规则：用Map存储每个需要检查的键（k），对应的值是一个Set，存放该键下需要排除的所有值。这一步的时间复杂度是O(m)，m是排除规则的数量。
2. 单次过滤遍历：只遍历一次items数组，对每个item，检查它在excludeMap中存在的键对应的值是否在排除集合里。只要有一个匹配就过滤掉，否则保留。这一步时间复杂度是O(n)，n是items数量。
3. 整体时间复杂度为O(n+m)，当n远大于m时，等价于O(n)，满足你的优化需求。

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