带去重的归并排序
答案要点
- 分治:左右两半分别排序去重,再归并
- 归并时相等元素只保留一个,两指针同时后移
- 子结果各自无重复,保证归并结果也无重复
- 递归需返回去重后的有效长度,归并按有效长度进行
- 时间 O(n log n),空间 O(n);也可排序后线性去重
易错点
- 只在归并时处理相等,却没保证子段内部已去重
- 归并后仍按原区间长度拷贝,混入无效数据
- 相等时只移动一个指针,导致重复元素被保留
面试官常见追问
- 如果要统计每个元素的重复次数呢?
- 链表上怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场