75. 颜色分类

75.颜色分类

题目：
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。

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

提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

思路：三指针

设计三个指针： 红色、绿色、蓝色 ，红色从左往右遍历、 绿色指针指向最左边，蓝色指向最右边

遇到0：红色指针跟绿色指针的值交换，绿色++ 红色++
遇到1：跳过 红色指针++
遇到2：红色指针跟蓝色指针的值交换，蓝色指针-- 然后再次对红色指针的值进行 0 1 2 的判断

class Solution {
    public void sortColors(int[] nums) {
        
        //0. 边界条件判断
        if(nums==null) return;

        //1.设l r i 指针 分辨表示左侧0 右侧2 遍历扫描
        int l = 0;
        int r = nums.length - 1;
        int i = 0;

        //2.遍历数组把0移动到左侧 2 移动到右侧 1保持在原地
        /**
         循环不变量：
         all in [0,l)     存放 0
         all in [l,i)     存放 1
         all in (r,len-1] 存放 2
         */
        while(i <= r) {
            int val = nums[i];
            if(val==0) {
              //把值为0的往左侧放，然后把l移动到下一个可以放0的位置
              swap(l++,i++,nums);
            }else if(val==1) {
               //继续扫描下一个，因为值为1的话不需要移动
               i++;
            }else {
                //把值为2的移动到右边，交换后需要再次判断i位置的值
               swap(i,r--,nums);
            }
        }
    }

    private void swap(int i,int j,int[] nums){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}