【Hot 100 刷题计划】 LeetCode 75. 颜色分类 | C++ 两次遍历双指针法

张开发
• 2026/4/12 22:42:21 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

【Hot 100 刷题计划】 LeetCode 75. 颜色分类 | C++ 两次遍历双指针法
LeetCode 75. 颜色分类 题目描述题目级别中等给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的sort函数的情况下解决这个问题。示例 1:输入nums [2,0,2,1,1,0]输出[0,0,1,1,2,2] 破题思路两次 Partition 划分这道题最直观的解法就是借用快速排序Quick Sort中划分区间Partition的思想。因为总共只有三种数字我们可以分两步走第一趟扫描准备左右两个指针。左指针找非0右指针找0然后把它们互换。这一趟结束后所有的0都被推到了数组的最前面。第二趟扫描再次初始化左右指针。左指针找非2右指针找2然后把它们互换。这一趟结束后所有的2都被推到了数组的最后面。经过这两步头部的0和尾部的2都归位了剩下的1自然就被挤在了数组的中间排序完成 C 代码实现 (两次遍历法)classSolution{public:voidsortColors(vectorintnums){intl0,rnums.size()-1;// 第一趟把所有的 0 换到最左边while(lr){while(lrnums[l]0)l;while(lrnums[r]!0)r--;if(lr){swap(nums[l],nums[r]);l,r--;}}// 第二趟把所有的 2 换到最右边l0,rnums.size()-1;while(lr){// 注意这里左指针只要不是 2 就往右走不用管 0 和 1while(lrnums[l]!2)l;while(lrnums[r]2)r--;if(lr){swap(nums[l],nums[r]);l,r--;}}}};

更多文章