有序向量：唯一化
看完你能说清 uniqfy 为何只需 O(n)，并写出低位紧凑的完整实现
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
有序向量：唯一化
看完你能说清 uniqfy 为何只需 O(n)，并写出低位紧凑的完整实现
什么是有序向量
上页发现：乱序判重要两两比较，代价高。若向量先排好序呢？就像整理过的书架，相同的书必然紧挨着——找重复只需看邻居，这正是唯一化的前提。
同类书相邻摆放，对应相等元素必然相邻
有序性蕴涵的结论
从左到右看有序向量：相等的元素必然相邻，扫描时只需比较相邻元素。
低效版算法思路
低效思路：两两比对相邻元素，发现重复就当场删掉，边扫边删。
低效版代码实现
逐个检查前驱并删除重复元素，看清 remove 的真实开销。
第 4 行发现重复即调用 remove(i) 删除，但 remove 本身要整体前移后续元素，单次就耗 O(n)；最坏情况总复杂度高达 O(n²)。
低效版的复杂度分析
沿箭头看：每发现一个重复，删除动作都要把整个后缀前移一次，累计成平方级代价。
换个思路：不删而是留
上一页的低效版总在事后补救：发现重复再删，反复搬动整个后缀。换个思路——既然已经有序，重复必然相邻，为什么不干脆一次扫描，把该留的元素直接搬到前面？
检录员不必清场，只把合规者引到前排，其余原地忽略
高效版算法流程
高效版唯一化：j 扫描全表，i 守住已保留区末尾，一趟完成去重。
高效版代码实现
几行代码完成原地唯一化：只留不删，一次遍历搞定。
j 扫描、i 收留不重复元素，全程一次遍历 O(n)；最后改 _size 即原地截断，无需逐个删除。
实例演示与分析
从左往右读：j 扫描全表，遇重复只前进 j，遇新元素才推进 i 并赋值，最后截断。
低效版 vs 高效版
两者都在去重，但「删」与「留」一字之差，复杂度差出一个数量级。
- 思想：发现重复就逐个删除
- 移动量：每次删除搬移 O(n) 后缀
- 复杂度：O(n²)，重复多时更慢
- 思想：不删，把保留者原地前压
- 移动量：每个元素最多搬一次
- 复杂度：O(n)，一趟扫描完成
自测一题
对含重复元素的有序向量做唯一化，为何能在 O(n) 时间内原地完成？
本讲要点
- ✓有序性把重复元素压缩成相邻段，这是前提
- ✓先找后删：逻辑区间覆盖，避免逐个 remove
- ✓只需一次遍历、O(n) 时间，无需额外空间
- ✓区间更新返回新逻辑长度，尾部旧元素不用清
- ✓无序向量不能这样做，需先排序再唯一化
课后思考
先自己琢磨，再对照参考答案——答案只是起点，不是终点。
参考答案不行。高效版靠相邻元素重合即可去重，本质依赖「相等元素必相邻」。无序时相等元素可散布各处，需哈希或先排序，比较的传递优势消失。
参考答案仿照「区间划分」套路：双指针扫描，不重复元素前移，重复段聚拢到后缀。返回重复区间的起点，调用者可自由处置这个后缀。
参考答案本算法是稳定的：仅前移、不交换，次序保持。当元素带附带数据（如按时间排序的记录）时，稳定性保证了去重不破坏语义。