[数据结构与算法]LeetCode 热题100-31-颜色分类

核心思想：双指针
内容：只需要处理=0和=2的情况，当把这两种处理好放在数组两端时，剩下的就是1的情况。
难点：for中while的想法，它可以完美处理注释中的情况，厉害！

class Solution {
    public void sortColors(int[] nums) {
        int len = nums.length;
        int p0 = 0;
        int p2 = len - 1;
        int mid = 0;
        //这里上届写成动态的，是为了保证运行时间为O(n)
        for(int i = 0; i <= p2; i++){
        	//这里为什么不用if，因为如果出现[2,..,2]的情况，这会原地打转，并且i之后还会++，
        	//导致2没有放到数组末尾；这里用while一是可以保证出现上述情况，p2的位置会向左移，
        	//进行置换，并且i这个位置也不会错过；二是随着p2的降低，数组上届也在变短，并没有浪费多余的运行时间。
            while(i <= p2 && nums[i] == 2) {
                mid = nums[i];
                nums[i] = nums[p2];
                nums[p2] = mid;
                p2--;
            }
            if(nums[i] == 0){
                mid = nums[p0];
                nums[p0] = nums[i];
                nums[i] = mid;
                p0++;
            }
        }
    }
}