只含 0、1、2 的数组排序(荷兰国旗问题)
哪些公司问过
答案要点
- 识别为荷兰国旗问题,可一趟扫描原地完成,时间 O(n)、空间 O(1)
- 维护 lt、i、gt 三个下标,分别划出小于区、等于区、大于区
- 遇 0 与 lt 交换且 lt、i 都前进;遇 2 与 gt 交换后 gt 后退而 i 不动;遇 1 则 i 前进
- 替代解法:计数排序统计三种数字个数后回填,需要两趟
- 推广到任意 pivot 即三路快排划分,适合有大量重复元素的数组
易错点
- 循环条件写成 i<gt,漏掉检查 gt 位置的元素
- 与 gt 交换后 i 也加一,导致换过来的 0 没被处理
- 边界没处理好,空数组或全是同一个数时下标越界
面试官常见追问
- 为什么和 gt 交换后 i 不能前进?
- 三路快排相比普通快排有什么优势?
- 如果有 k 种颜色怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 快速排序的原理与实现155 场
- 常见排序算法的对比129 场
- 排序算法的稳定性58 场
- 归并排序的实现与特点24 场
- 堆排序的实现21 场
- 外排序:10 亿个整数如何排序14 场
- C++ std::sort 的内部实现7 场
- 手写实现一种数组排序算法7 场
- 快速排序的最坏情况与优化方法7 场
- 冒泡排序与快速排序的原理与区别6 场