如何手写数组去重？不同方案有什么区别？

简化版

数组去重最常用 Set：[...new Set(arr)]，时间复杂度通常是 O(n)。手写时要能说明 Set 使用 SameValueZero 语义，NaN 能被去重，0 和 -0 会被视为相同；对象去重则要按引用或业务 key 另行处理。

详细版

简单值去重可写成：

function unique(arr) {
  return [...new Set(arr)]
}

若要保留第一次出现的对象，可按 key 去重：

function uniqueBy(arr, getKey) {
  const seen = new Set()
  const result = []
  for (const item of arr) {
    const key = getKey(item)
    if (!seen.has(key)) {
      seen.add(key)
      result.push(item)
    }
  }
  return result
}

面试重点不是只背 Set，而是比较 indexOf、双循环、排序去重、Map/Set 去重的语义差异，尤其是 NaN、对象引用和是否保留原始顺序。

完整版教学

一、先确定“重复”的定义

数组去重不是一个固定答案，而是先定义相等规则。简单类型可以按值比较，对象可能按引用、按 id、按多个字段组合比较。

输入	去重规则	结果
`[1, 1, 2]`	数值相等	`[1, 2]`
`[NaN, NaN]`	SameValueZero	`[NaN]`
`[{id:1},{id:1}]`	引用相等	两个都保留
`[{id:1},{id:1}]`	`id` 相等	保留一个

易错点：对象“长得一样”不等于引用相同，业务去重必须先说清 key。

二、`Set` 去重

function unique(arr) {
  return Array.from(new Set(arr))
}

unique([1, 1, NaN, NaN, 0, -0]) // [1, NaN, 0]

Set 保持插入顺序，所以返回结果会保留第一次出现的顺序。它的相等语义是 SameValueZero，能把 NaN 识别为相同，也会把 0 和 -0 视为相同。

三、`indexOf` 方案的陷阱

function uniqueByIndexOf(arr) {
  const result = []
  for (const item of arr) {
    if (result.indexOf(item) === -1) result.push(item)
  }
  return result
}

uniqueByIndexOf([NaN, NaN]) // [NaN, NaN]

indexOf 使用严格相等风格的比较，NaN !== NaN，所以无法去掉重复的 NaN。同时每次查找都要扫描结果数组，最坏时间复杂度是 O(n^2)，数据量大时不如 Set。

四、排序去重的取舍

function uniqueSorted(arr) {
  const sorted = [...arr].sort((a, b) => a - b)
  const result = []
  for (const item of sorted) {
    if (result.length === 0 || !Object.is(result[result.length - 1], item)) {
      result.push(item)
    }
  }
  return result
}

排序后相同值相邻，去重只需和前一个元素比较。代价是复杂度通常为 O(n log n)，并且输出顺序变成排序顺序，不再保留原数组第一次出现顺序。

五、对象数组按 key 去重

function uniqueBy(arr, getKey) {
  const seen = new Map()
  for (const item of arr) {
    const key = getKey(item)
    if (!seen.has(key)) seen.set(key, item)
  }
  return [...seen.values()]
}

uniqueBy([{ id: 1, name: 'A' }, { id: 1, name: 'B' }], x => x.id)

上面保留第一次出现的元素。如果要保留最后一次，可以每次都 seen.set(key, item)，但要明确顺序语义。多个字段组合 key 时不要随手拼接成 a + b，因为 ['1','23'] 和 ['12','3'] 都可能变成 '123'，更稳妥的是使用分隔符或结构化序列化。

六、复杂度和场景选择

方案	时间复杂度	是否保序	适合场景
`Set`	通常 `O(n)`	保留首次顺序	简单值去重
`indexOf`	`O(n^2)`	保留首次顺序	小数组、兼容旧环境
排序去重	`O(n log n)`	不保原顺序	需要排序结果
`Map + key`	通常 `O(n)`	可控	对象数组业务去重

如果输入只有 10 个元素，方案差异几乎感受不到；如果输入有 100000 个元素，indexOf 双重扫描就会明显慢很多。面试时给出这个量级感，会比只说复杂度更可信。

七、常见误区与追问

误区：数组去重只有 Set 一个答案。 Set 适合简单值，对象业务去重要按 key。
误区：indexOf 能处理所有值。 它无法正确去重重复的 NaN。
误区：排序去重一定更快。 排序有 O(n log n) 成本，还会改变原始顺序。
追问：0 和 -0 怎么办？ Set 会把它们视为相同，若要区分需用自定义规则。
追问：对象内容相同会被 Set 去重吗？ 不会，不同对象引用会被视为不同值。
追问：保留最后一次怎么写？ Map 中重复 key 时覆盖旧值，再返回 values。

八、加强记忆

数组去重先问“按什么相等”。简单值优先 Set，对象按业务 key 用 Map，小数组兼容可用 indexOf，需要排序结果才考虑排序去重。看到 NaN、对象、保序、保留首次或末次这几个词，就要意识到这题在考相等语义，而不只是考 API 熟练度。

简化版

详细版