颜色分类（中等）

题目描述

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例1

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例2

输入：nums = [2,0,1]
输出：[0,1,2]

做题思路

方法一：重写数组

1. 统计数组中0，1，2的个数

2. 根据0，1，2的个数重写数组

方法二：单指针

1. 对数组进行两次遍历

2. 第一次遍历，我们将数组中所有的0交换到数组的头部

3. 第二次遍历，我们将数组中所有的1交换到头部的0之后

4. 两次遍历结束后，所有的2都出现在数组的尾部

方法三：双指针

1. 设置指针p0交换0，p2交换2

2. p0的初始值为0，p2的初始值为len-1

3. 从左向右遍历整个数组，设当前遍历到的位置为i，对应的元素为nums[i]

- 若i指向0，与p0指向的元素交换，p0++

- 若i指向2，与p2指向的元素交换，p2--，在这个过程中，我们需要不断地将其与nums[p2]进行交换，直至新的nums[i]不为2（因为如果二者交换之后，i指向的元素依然是2，直接开始遍历下一个元素，不再考虑当前元素了，这样会得到错误的答案，即2可能不是在数组的尾部）

代码

重写数组

class Solution {
    public void sortColors(int[] nums) {
        int len=nums.length;
        int n0=0,n1=0,n2=0;
        //统计0，1，2的数量
        for(int num:nums){
            if(num==0){
                n0++;
            }else if(num==1){
                n1++;
            }else{
                n2++;
            }
        }
        //根据0，1，2的个数重写数组
        for(int i=0;i<len;i++){
            if(i<n0){
                nums[i]=0;
            }else if(i<n0+n1){
                nums[i]=1;
            }else{
                nums[i]=2;
            }
        }
    }
}

单指针

class Solution {
    public void sortColors(int[] nums) {
        int len=nums.length;
        int p=0;
        //将所有0元素交换到数组前端
        for(int i=0;i<len;i++){
            if(nums[i]==0){
                int temp=nums[i];
                nums[i]=nums[p];
                nums[p]=temp;
                p++;
            }
        }
        //将所有1元素交换到0元素的后面
        for(int i=p;i<len;i++){
            if(nums[i]==1){
                int temp=nums[i];
                nums[i]=nums[p];
                nums[p]=temp;
                p++;
            }
        }
    }
}

双指针

class Solution {
    public void sortColors(int[] nums) {
        int len=nums.length;
        int p0=0,p2=len-1; //设置双指针，p0指向数组头元素，p2指向数组尾元素
        for(int i=0;i<=p2;i++){
            //当i指向2时，我们需要不断地将nums[i]与nums[p2]进行交换，直至nums[i]不为2
            while(i<=p2&&nums[i]==2){ 
                int temp=nums[i];
                nums[i]=nums[p2];
                nums[p2]=temp;
                p2--;
            }
            //当i指向0时，将nums[i]与nums[p0]进行交换
            if(nums[i]==0){
                int temp=nums[i];
                nums[i]=nums[p0];
                nums[p0]=temp;
                p0++;
            }
        }
    }
}