面试题库 › C++ / 后端 › 只含 0、1、2 的数组排序(荷兰国旗问题)

只含 0、1、2 的数组排序(荷兰国旗问题)

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:排序算法

哪些公司问过

字节跳动2腾讯1

常见岗位:后端开发、Go 后端、Python 后端

答案要点

  1. 识别为荷兰国旗问题,可一趟扫描原地完成,时间 O(n)、空间 O(1)
  2. 维护 lt、i、gt 三个下标,分别划出小于区、等于区、大于区
  3. 遇 0 与 lt 交换且 lt、i 都前进;遇 2 与 gt 交换后 gt 后退而 i 不动;遇 1 则 i 前进
  4. 替代解法:计数排序统计三种数字个数后回填,需要两趟
  5. 推广到任意 pivot 即三路快排划分,适合有大量重复元素的数组

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题