面试题库 › 客户端 › 荷兰国旗问题(三指针划分)

荷兰国旗问题(三指针划分)

难度 ★★☆在 2 场真实面经中被问到 方向:客户端考点:数组与字符串

哪些公司问过

小红书2

常见岗位:安卓

答案要点

  1. 目标:只含 0、1、2 的数组原地排序,一次遍历
  2. 三指针:low 放 0 的位置,high 放 2 的位置,cur 当前扫描位置
  3. 遇 0 与 low 交换,low 和 cur 都加一;遇 1 则 cur 加一
  4. 遇 2 与 high 交换,high 减一,cur 不动,因为换来的数未检查
  5. 循环条件 cur 不超过 high;时间 O(n),空间 O(1);三路划分思想用于快排

易错点

面试官常见追问

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

相关面试题