hot100-75 颜色分类

题目描述

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

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

示例 1：

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

思路

快速排序（partition）
循环不变量

什么是 partition ？

我们在学习快速排序的时候知道，可以选择一个标定元素（称为 pivot ，一般而言随机选择），然后通过一次扫描，把数组分成三个部分：

第 1 部分严格小于 pivot 元素的值；
第 2 部分恰好等于 pivot 元素的值；
第 3 部分严格大于 pivot 元素的值。
第 2 部分元素就是排好序以后它们应该在的位置，接下来只需要递归处理第 1 部分和第 3 部分的元素。

经过一次扫描把整个数组分成 3 个部分，正好符合当前问题的场景。写对这道题的方法是：把循环不变量的定义作为注释写出来，然后再编码。

循环不变量定义

循环不变量：声明的变量在遍历的过程中需要保持定义不变。

设计循环不变量的原则
说明：设计循环不变量的原则是 不重不漏。

len 是数组的长度；
变量 zero 是前两个子区间的分界点，一个是闭区间，另一个就必须是开区间；
变量 i 是循环变量，一般设置为开区间，表示 i 之前的元素是遍历过的；
two 是另一个分界线，我设计成闭区间。

如果循环不变量定义如下：

所有在子区间 [0, zero) 的元素都等于 0；
所有在子区间 [zero, i) 的元素都等于 1；
所有在子区间 [two, len - 1] 的元素都等于 2。

于是编码要解决以下三个问题：

变量初始化应该如何定义；
在遍历的时候，是先加减还是先交换；
什么时候循环终止。
处理这三个问题，完全看循环不变量的定义。

编码的时候，zero 和 two 初始化的值就应该保证上面的三个子区间全为空；
在遍历的过程中，「下标先加减再交换」、还是「先交换再加减」就看初始化的时候变量在哪里；
退出循环的条件也看上面定义的循环不变量，在 i == two 成立的时候，上面的三个子区间就正好不重不漏地覆盖了整个数组，并且给出的性质成立，题目的任务也就完成了。

代码

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        if(len<2)return;
        int zero = 0;
        int two = len;
        int i = 0;
        while(i<two){
            if(nums[i]==0){
                swap(nums,i,zero);
                zero++;
                i++;
            }else if(nums[i]==1){
                i++;
            }else{
                two--;
                swap(nums,i,two);
            }
        }
    }

    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

或者

以[2 0 2 1 1 1 0]为例大致可以这样理解：

[2 0 2 1 1 1 0]
-> [2 2 2 2 2 2 2] 先全填上2
-> [1 1 1 1 1 2 2] 统计下0和1的个数之和(作为数字1的右侧边界)，然后填上1
-> [0 0 1 1 1 2 2] 统计下0的个数（作为数字0的右侧边界），然后填上0

    public void sortColors(int[] nums) {
        int one = 0,zero = 0;
        for(int i = 0; i<nums.length; i++){
            int tmp = nums[i];
            nums[i] = 2;
            if(tmp <= 1){
                nums[one] = 1;
                one++;
            }
            if(tmp == 0){
                nums[zero] = 0;
                zero++;
            }
        }
    }