题目与范围
给定固定整数宇宙 [0, U)，实现一个集合，支持 insert(x)、remove(x)、contains(x)、clear() 和遍历当前元素。要求前四项为最坏 O(1)，遍历为当前元素数 O(k)。集合不允许重复值，删除不存在的值不报错。
公开面经记录了 Pure Storage 的同型题目；题目真正考察的是 dense/sparse 数组不变量，而不是记忆某个库的类名。
面试官考察什么
- 是否明确固定宇宙是前提，不能把
O(1)结论无条件推广到任意整数。 - 是否同时维护
dense[sparse[x]] == x，并用它避免删除后的误判。 - 删除是否采用末元素交换，从而保持 dense 前缀连续且遍历为
O(k)。 - 是否说明空间为
O(U)，当集合很稠密或宇宙未知时应考虑其他结构。
作答前澄清
U是否已知且可接受两条长度为U的数组？这是稀疏集合成立的资源前提。iterate()是否要求排序？本方案只保证遍历全部成员，不保证顺序。- 是否需要稳定迭代器或并发访问？若需要，交换删除和同步策略都要重新定义。
clear()是否必须避免扫描U？本题要求常数时间，因此只重置size。
30 秒回答
“我维护长度为 U 的 sparse 索引和长度为 U 的 dense 数组，再保存当前 size。元素 x 存在，当且仅当 sparse[x] < size 且 dense[sparse[x]] == x。插入把 x 写到 dense[size] 并记录索引；删除时用最后一个元素覆盖被删位置并修正它的索引；清空只把 size 置零。四个核心操作都是最坏 O(1)，遍历 dense 的前 size 个位置是 O(k)，空间是 O(U)。”
分步深答
第一步：定义不变量。
dense[0..size) 保存全部成员且没有重复；如果 x 在集合中，则 sparse[x] 是它在 dense 中的位置，且 dense[sparse[x]] == x。对不在集合中的值，sparse 内容可以是旧值，所以 contains 不能只检查索引范围。
第二步：查询与插入。
contains(x) 先检查 0 <= x < U，再验证 sparse[x] < size 和反向链接。插入先调用 contains；若不存在，把它写入 dense[size]，设置 sparse[x] = size，最后递增 size。
第三步：交换删除。
若 x 在位置 i，令 last = dense[size - 1]，把 last 写入 dense[i]，更新 sparse[last] = i，再递减 size。无需清理 sparse[x]，因为 size 变化后反向链接校验会使它失效；删除最后一个元素也遵循同一流程。
第四步：常数时间清空与线性遍历。
clear() 只设置 size = 0，旧数组内容不会被读取为有效成员。遍历只扫描 dense[0] 到 dense[size - 1]，因此耗时是 O(k)，而不是 O(U)。
第五步：复杂度与适用边界。
contains、insert、remove、clear 都是最坏 O(1)；遍历是 O(k)；空间是 O(U)。GCC 的实现还指出，稀疏集合适合固定宇宙且需要密集遍历的场景；宇宙未知、需要扩容或 U 远大于可用内存时，哈希集合或位图可能更合适。
第六步：测试不变量。
用参考 Set 逐次对照随机操作。覆盖空集合、重复插入、删除不存在值、删除中间元素、删除最后元素、清空后复用、0 与 U-1，并在每次操作后验证 dense 前缀无重复、每个成员的反向链接成立。
高质量示范回答
“固定宇宙 [0, U) 让我可以用两个数组换取确定的常数时间。dense 保存当前成员的紧凑前缀，sparse 把值映射回 dense 下标；成员判断必须同时检查边界、下标小于 size 和反向链接，不能只看 sparse 数值。删除用最后元素覆盖目标位置并更新其 sparse 下标，clear 只重置 size。这样更新和查询是最坏 O(1)，遍历是 O(k)，空间是 O(U)；当宇宙不可控时我会改用哈希表或位图。”
常见错误
- 只判断
sparse[x] < size→ 未加入的值可能残留合法下标 → 补上dense[sparse[x]] == x。 - 删除后整体搬移 → 删除退化为
O(U)或O(k)→ 用最后元素交换。 - 把 clear 写成填零循环 → 清空变成
O(U)→ 只重置 size。 - 忽略固定宇宙 → 数组索引越界或内存不可接受 → 先确认
[0, U)与容量约束。 - 声称遍历是 O(1) → 取到视图是常数，处理全部元素仍需
O(k)→ 区分返回视图与消费元素。
追问与回答
追问 1：如何支持任意整数？
先做坐标压缩，把实际值映射到 [0, U)；若值域持续增长或无法预扫描，哈希集合更自然，但其常数时间是均摊或期望意义，不能复用本题的最坏 O(1) 结论。
追问 2：如何保证遍历顺序？
当前 dense 的顺序会被交换删除改变。若要求插入顺序，需要额外链表或稳定数组，删除和空间开销都会变化；应先确认顺序是否属于接口合同。
追问 3：什么时候选择位图？
若只需要成员判断、宇宙规模适中且希望每个值占一位，位图更省空间。若还需要快速枚举成员，稀疏集合的 dense 前缀通常更适合；最终选择取决于 U、成员数和访问模式。