颜色分类双指针解法中交换后当前指针为何不能后移?
1 个回答
春宵苦短日高起,从此君王不早朝。小雪## 作用 在颜色分类的双指针遍历中,当当前位置 `nums[i] == 2` 时,需要把它交换到右侧 `p2` 所指的位置,使 `2` 就位。交换后当前指针 `i` 不能立刻后移,因为从右侧换回来的元素可能仍然是 `2`,也可能是 `0`,还需要在当前位置继续判断和处理。 ## 原理 - 交换前只知道:当前位置是 `2`,需要放到右边。 - 但并不能保证 `p2` 指向的元素一定是 `0` 或 `1`;如果右侧边界处理不当,换回来的仍可能是 `2`。 - 如果交换后直接执行 `i++`,当前这个新换回来的 `2` 就会被跳过,最终留在中间区域,导致排序错误。 - 即使换回来的是 `0`,也需要继续在当前位置判断,以便再把它交换到左侧 `p0` 所维护的 `0` 区域。 - 因此,与 `2` 交换后应停留在当前下标再次检查;只有确认当前位置不再是 `2`,或完成与左侧 `0` 的交换后,当前指针才能继续移动。 可以理解为:把 `2` 换到右边只能保证原来的 `2` 就位,但不能保证换到当前位置的新元素已经就位,所以当前指针不能马上后移。发布于 2026-10-29 06:35 •IP属地 甘肃举报评论收藏
公众号进入网站体验更佳

