一、编程题：75. 颜色分类（双指针，循环不变量）
1.题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。 LeetCode题目链接。
2.示例1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
3.示例2：
输入：nums = [2,0,1]
输出：[0,1,2]。
4.提示：
- n == nums.length
- 1 <= n <= 300
- nums[i] 为 0、1 或 2
5.进阶：
- 你可以不使用代码库中的排序函数来解决这道题吗？
- 你能想出一个仅使用常数空间的一趟扫描算法吗
二、解题思路
1.思路
解决方法1（个人想法）：
- Step1.创建三个变量用于存储0，1，2出现的个数；
- Step2.用for循环遍历数组，计算出0，1，2出现的个数；
- Step3.再用for循环根据0，1，2出现的个数对数组进行重写即可；
解决方法2（双指针，循环不变量）：官方视频讲解
- Step1.定义循环不变量，
all in [0, left) == 0
all in [left, i) == 1
all in (right, len - 1] == 2 - Step2.创建两个指针left，right，其中left=0，right=nums.length-1，left指针用于指向最左边的位置，rigtht指针指向最右边的位置；
- Step3.当nums[i] == 0时，则与最右边的位置left进行交换，交换之后则left要自加1，并且i自加1（这里用for循环进行遍历时，i不用考虑自加）；
- Step4.当nums[i] == 2时，则与最左边的位置right进行交换，交换之后right要自减1，并保持i不变（这里用for循环时，i要自减1）；
- Step5. 用for实现该双指针时，不需要考虑Step5。 当nums[i] == 1时，不做处理，让循环i自加1即可；
三、代码实现
。每个代码块都写了注释，方便理解，代码还可以改进；
代码如下（示例）：
解法一：
class Solution { public void sortColors(int[] nums) { //第一种方法（分组） int zero = 0, one = 0, two = 0; for(int right = 0; right < nums.length; right++){ switch(nums[right]){ case 0: zero++;break; case 1: one++;break; case 2: two++;break; } } // System.out.println("zero="+zero+" one="+one+" two="+two); for(int right = 0; right < nums.length; right++){ if(zero > 0){ nums[right] = 0; zero--; }else if(one > 0){ nums[right] = 1; one--; }else if(two > 0){ nums[right] = 2; two--; } } } }
解法二：
- for循环实现
class Solution { public void sortColors(int[] nums) { //第二种方法（双指针） // 循环不变量 // all in [0, p0) == 0 红 // all in [p0, i) == 1 白 // all in (p2, len - 1] == 2 蓝 // 把红色和蓝色放在两边，中间自然就是白色 int left = 0, right = nums.length - 1; //for循环实现 for(int i = 0; i < right+1; i++){ switch(nums[i]){ case 0: swap(nums, left++, i); break; case 2: //当值为2时，则进行交换，并把right指针自减1并保持i不变 swap(nums, i--, right--); break; } } } public void swap(int[] nums, int left, int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } }
- while循环实现
class Solution { public void sortColors(int[] nums) { //第二种方法（双指针） // 循环不变量 // all in [0, p0) == 0 红 // all in [p0, i) == 1 白 // all in (p2, len - 1] == 2 蓝 // 把红色和蓝色放在两边，中间自然就是白色 int left = 0, right = nums.length - 1; //while循环实现 int i = 0; while(i <= right){ switch(nums[i]){ case 0: swap(nums, left++, i++); break; case 1: i++; break; case 2: swap(nums, i, right--); break; } } } public void swap(int[] nums, int left, int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } }
提交结果：
总结
以上就是今天要讲的内容，一开始做题的时候，首先想到就是用for循环遍历计数，然后再用for循环重写原数组，后面看了官方视频讲解之后，接触到一个新概念：循环不变量，根据循环不变量以及双指针思想在对该题进行理解，对双指针思想的印象很深刻，所以就赶紧记录一下这个方法，开阔一下思路。
感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹 🌹 🌹
也欢迎你，关注我。👍 👍 👍
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
