如何以线性时间O(N)实现多值数组过滤？

可以把时间复杂度优化到O(n + m)（线性时间，n为data数组长度，m为filterBy数组长度），核心优化方向是将用于匹配的filterBy数组转换为哈希集合（Set），利用集合的常数时间查找特性替代数组的线性查找。

原代码问题分析 #

原代码中data.filter(x => filterBy.includes(x))的时间复杂度是O(n*m)：

• filter方法遍历data数组，时间复杂度O(n)
• 每次调用filterBy.includes(x)都会遍历filterBy数组，时间复杂度O(m)
  当data和filterBy都包含大量元素时，整体复杂度会趋近于O(n²)，性能会显著下降。

优化后的代码示例 #

const data = ['a', 'b', 'c', 'd'];
const filterBy = ['c', 'a'];

// 将filterBy转换为Set
const filterSet = new Set(filterBy);
// 利用Set的has方法（O(1)时间）进行过滤
const r = data.filter(x => filterSet.has(x));
console.log(r); // 输出: ['a', 'c']

优化原理 #

• 转换Set的过程是O(m)时间，仅需执行一次
• 后续filter遍历data时，每次filterSet.has(x)的查找时间是O(1)，所以整体时间复杂度为O(n + m)，属于线性时间范畴，在数据量较大时性能提升非常明显。

额外说明 #

如果需要保留原filterBy数组的重复值（比如过滤时要匹配多次），Set会自动去重，这种情况可以改用Map记录元素的出现次数，但大多数过滤场景中，仅需判断元素是否存在，Set完全够用。

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