75：颜色分类

问题描述

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

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

注意:
不能使用代码库中的排序函数来解决这道题。

示例

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

进阶：

• 一个直观的解决方案是使用计数排序的两趟扫描算法。
• 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

问题分析

这题咱们完全可以扫描一趟解决。我们扫描每一个元素，把每个元素放到它该在的地方即可。
对于0的处理：跟待处理序列的第一个元素互换。
对于2的处理：跟待处理序列的最后一个元素互换。
对于1的处理：跳过。

等等！我们这样弄的话，比如用0换来了2，怎么办？没错。我们要对这种情况进行处理。但是写一堆if-else简直太low了。我们完全不需要改变计数器的值，让它在下次循环进行判定。

再等等！对于2,1,0来说，初始待处理序列是2,1,0.
我们对2进行处理后，序列为：0,1,2。待处理序列为0,1。
我们对0进行处理，发现它应该与自己互换。即没有处理。所以此时待处理序列变成了1. 但是此时我们的计数器还没更新呢？咋整？

对，我们应该更新计数器。何时更新？

• 我们要保证计数器指向待处理序列的头部。

AC代码：

package program;

import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        int[] arr = {2,1,0};
        Solution solution = new Solution();
        solution.sortColors(arr);
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int left = 0,right = nums.length-1;
        //left,right分别指向0和2的待交换位置
        int i = left;
        while(i <= right){
            // 计数器要指向待处理序列的头部
            if(nums[i] == 1 || i < left){
                i++;
            }
            else if(nums[i] == 0){
                this.swap(nums,i,left++);
            }
            else if(nums[i] == 2){
                this.swap(nums,i,right--);
            }
        }
    }
    private void swap(int[] nums,int i,int j){
        if(i == j){
            return;
        }
        nums[i] = nums[i]^nums[j];
        nums[j] = nums[i]^nums[j];
        nums[i] = nums[i]^nums[j];
    }
}