75. 颜色分类

解法一：计数排序

统计出现频率，然后原地修改。常数级空间但是需要两趟扫描。

class Solution {
    public void sortColors(int[] nums) {
        int[] cnt = new int[3];
        for (int i : nums) {
            ++cnt[i];
        }
        int index = 0;
        for (int color = 0; color < 3; ++color) {
            for (int i = 0; i < cnt[color]; ++i) {
                nums[index++] = color;
            }
        }
    }
}

解法二：双指针

参考官方题解：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode-solution/

class Solution {
    public void sortColors(int[] nums) {
        int p0, p1;
        p0 = p1 = 0;
        for (int i = 0; i < nums.length; ++i) {
            switch (nums[i]) {
                case 1:
                    nums[i] = nums[p1];
                    nums[p1] = 1;
                    ++p1;
                    break;
                case 0:
                    nums[i] = nums[p1];
                    nums[p1] = 1;
                    nums[p0] = 0;
                    ++p0;
                    ++p1;
            }
        }
    }
}