颜色分类

75. 颜色分类

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

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

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

示例:

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

进阶：

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

方法一：单指针

使用两次遍历，第一次遍历将所有的 0 交换到数组头部，第二次遍历将所有的 1 交换到数组头部的 0 之后。

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;
        for(int i = 0; i < n; ++i){
            if(nums[i] == 0){
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }

        for(int i = ptr; i < n; ++i){
            if(nums[i] == 1){
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr] = temp;
                ++ptr;
            }
        }
    }
}

方法二：双指针

使用 p0 指针维护数组前部的 0 ，使用 p2 指针维护数组后部的 2 。在遍历的过程中，我们需要找出所有的 0 交换至数组的头部，找出所有的 2 交换至数组的尾部。

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

• 如果 nums[i] = 0，将其与 nums[p0] 交换，将 p0 后移一个位置；
• 如果 nums[i] = 2，将其与 nums[p2] 交换，将 p2 前移一个位置；

对于第二种情况，交换后 nums[i] 可能为 2 ，也可能为 0。当我们找到 2 时，需要不断地将其与 nums[p2] 进行交换，直到新的 nums[i] 不为 2。

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for(int i = 0; i <= p2; ++i){
            while(i <= p2 && nums[i] == 2){
                nums[i] = nums[p2];
                nums[p2] = 2;
                --p2;
            }

            if(nums[i] == 0){
                nums[i] = nums[p0];
                nums[p0] = 0;
                ++p0;
            }
        }
    }
}