数组去重与不重复随机递增数组

高频真题解析与9月考点预测上.pdf 给出了数组去重的多种写法，高频真题解析与9月考点预测中.pdf 又给出了“生成不重复递增随机数组”的手写题。两道题看似都在处理重复值，实际契约不同：去重是确定性的集合投影，随机数组是带均匀性约束的抽样。

1. 稳定去重

1.1 原始值去重

如果题目只包含原始值，并要求保留第一次出现的顺序，Set 是最直接的实现。它采用 SameValueZero 规则：NaN 与自身相等，-0 与 0 视为同一个值；对象则按引用比较。

function uniqueValues(values) {
  return [...new Set(values)]
}

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

时间复杂度平均为 O(n)，额外空间（不计返回数组）为 O(n)。filter + indexOf 和 reduce + includes 也能保序，但查找是线性的，最坏为 O(n^2)；不要在大输入上只因为代码短就声称它们是 O(n)。

1.2 按键去重对象

对象数组通常不是按引用去重，而是按业务键（如 id）保留第一条或最后一条。把策略写进函数参数，避免把隐式覆盖当成需求：

function uniqueBy(items, keyOf, { keep = 'first' } = {}) {
  if (keep !== 'first' && keep !== 'last') {
    throw new RangeError("keep must be 'first' or 'last'")
  }

  const seen = new Map()
  for (const item of items) {
    const key = keyOf(item)
    if (keep === 'first' && seen.has(key)) continue
    seen.set(key, item)
  }

  return [...seen.values()]
}

uniqueBy(
  [{ id: 1, name: 'old' }, { id: 1, name: 'new' }, { id: 2, name: 'x' }],
  (item) => item.id
)
// [{ id: 1, name: 'old' }, { id: 2, name: 'x' }]

Map 中键的相等规则仍要明确。若键是大小写不敏感的字符串，应在 keyOf 中规范化；若需要深度相等，先定义可稳定序列化或哈希的规则，不能直接 JSON.stringify 后假定对象键顺序永远一致。

1.3 去重题的面试追问

需要保留最后一次时可从右向左扫描，或使用上面的 keep: 'last'；输出顺序是否仍按第一次位置，需要额外稳定化。
需要原地修改时，Set 方案会新建数组；必须先确认“原地”是否是硬约束。
Set 只保证插入顺序，不负责排序；去重和排序应分成两个步骤说明。
异步分页去重还要处理跨页 id、删除事件和版本冲突，不能只在单页调用 new Set。

2. 无重复递增随机数组

题面：给定 count 和最大值 max，从整数区间 [0, max] 中随机选择 count 个互不重复的值，最后按升序返回。可行的必要条件是 0 <= count <= max + 1。PDF 中“m >= n 就报错”的条件少算了一个端点：当范围是 [0, n] 时，最多可以取 n + 1 个值。

2.1 简单 Set 重试法

function randomIncreasingByRetry(count, max, random = Math.random) {
  validateSampleArgs(count, max)
  const selected = new Set()

  while (selected.size < count) {
    selected.add(Math.floor(random() * (max + 1)))
  }
  return [...selected].sort((a, b) => a - b)
}

function validateSampleArgs(count, max) {
  if (!Number.isInteger(count) || !Number.isInteger(max)) {
    throw new TypeError('count and max must be integers')
  }
  if (count < 0 || max < 0 || count > max + 1) {
    throw new RangeError('count must be in [0, max + 1]')
  }
}

循环每次抽样的碰撞概率会随着集合变满而升高，因此 count 接近 max + 1 时，运行时间的期望值明显变差；它不是严格的 O(count) 上界。排序成本为 O(count log count)，集合和结果占用 O(count) 空间。随机数生成器必须满足 [0, 1) 的契约，测试时可以注入确定性函数。

2.2 Floyd 抽样：不靠碰撞重试

当 max 很大而 count 较小时，可以用 Floyd 算法在 O(count) 次抽样中得到无重复集合，再排序：

function randomIncreasing(count, max, random = Math.random) {
  validateSampleArgs(count, max)
  const selected = new Set()

  // 从最后 count 个候选的边界开始，每轮只做一次随机选择。
  for (let j = max - count + 1; j <= max; j += 1) {
    const candidate = Math.floor(random() * (j + 1))
    selected.add(selected.has(candidate) ? j : candidate)
  }

  return [...selected].sort((a, b) => a - b)
}

抽样阶段是 O(count) 时间和 O(count) 空间，排序后总时间为 O(count log count)。算法的正确性依赖随机源均匀；Math.random 不适合安全令牌、抽奖审计或密码学场景，应改用 crypto.getRandomValues 并处理无偏映射。

2.3 如何证明“不重复”和“递增”

selected 是 Set，每轮只会保留一个新元素，因此最终大小恰为 count。
返回前对集合做数值升序排序，所以相邻元素严格递增。
若 count === 0，循环不执行，返回空数组；若 count === max + 1，结果必为 [0, 1, ..., max]。
不能用默认 .sort()，否则会按字典序把 [2, 10] 排成 [10, 2]。

3. 边界样例与验证

const seeded = (() => {
  let state = 123456789
  return () => {
    state = (1103515245 * state + 12345) % 2 ** 31
    return state / 2 ** 31
  }
})()

const result = randomIncreasing(5, 20, seeded)
console.assert(result.length === 5)
console.assert(result.every((value, i) => i === 0 || value > result[i - 1]))

面试时至少讨论：空数组、取满整个范围、count > max + 1、重复随机值、负数参数、默认排序器、输入是否允许修改，以及随机性是否需要可复现。若题目实际要求“随机排列”而不是“递增数组”，不要额外排序；若要求每个整数等概率，说明抽样算法和随机源的偏差处理。

来源：高频真题解析与9月考点预测上.pdf 的“数组去重”、高频真题解析与9月考点预测中.pdf 的“无序递增数组”。

相关专题：Set 与 Map 解题套路、排序算法对比、复杂度分析。