第 3 讲 · JavaScript 数组去重

我根据源目录中的 JavaScript 数组去重练习整理这一讲；原始完整题面没有保留。

问题的本质

输入是一个可能有重复值的数组，输出只保留每个值的第一次出现：

[22, 17, 22, 44, 44, 66, 17, 66, 7]
                  ↓
[22, 17, 44, 66, 7]

如果希望保留原始顺序，就不能只说“先排序再删相邻项”，因为排序已经改变了顺序。

最直接的解法：维护已见过集合

源代码维护结果数组 b。处理第 ii 个输入前，它始终满足一个不变式：

b 恰好包含前 ii 个输入中已出现的不同值，并按第一次出现的顺序排列。

const result = [];

for (const value of input) {
  let seen = false;
  for (const saved of result) {
    if (saved === value) {
      seen = true;
      break;
    }
  }
  if (!seen) result.push(value);
}

外层遍历 nn 个元素，内层最多再查 nn 个已保留元素，所以最坏时间复杂度是 O(n2)O(n^2)，额外空间是 O(n)O(n)。

为什么 Set 更适合

Set 直接表达“一组不重复的值”：

const result = [...new Set(input)];

等价的展开写法是：

const seen = new Set();
const result = [];

for (const value of input) {
  if (!seen.has(value)) {
    seen.add(value);
    result.push(value);
  }
}

哈希集合的查找平均可视为 O(1)O(1)，整体平均时间复杂度为 O(n)O(n)。它也继续保留首次插入顺序。

容易忽略的边界

== 与 ===

原作品使用 ==，它会进行类型转换，例如 1 == "1" 为真。在没有明确转换需求时，优先用 ===，可以避免数字和字符串被意外当成同一个值。

对象的“相等”

{} === {} // false

两个内容一样的对象也是两个不同引用，Set 不会自动按对象字段去重。对象数组通常要选一个业务唯一键，例如 id，再用 Map 记录。

怎么验证

至少要试这些情况：

  • 空数组；
  • 只有一个元素；
  • 全部相同；
  • 全部不同；
  • 重复值分布在首尾；
  • 数字与字符串混合时，是否应视为不同值。

评论