给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

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

class Solution {
    public void sortColors(int[] nums) {
      // 表示0, 1, 2三个元素的个数
        int zeroCount = 0, oneCount = 0, twoCount = 0;
        for (int num : nums) {
          // 判断数字，同时对应的个数加1
            switch (num) {
                case 0:
                    zeroCount++;
                    break;
                case 1:
                    oneCount++;
                    break;
                default:
                    twoCount++;
            }
        }
        // 最后分别按照3个元素的个数修改数组中的元素即可
        for (int i = 0; i < nums.length; i++) {
            if (zeroCount > 0) {
                nums[i] = 0;
                zeroCount--;
            } else if (oneCount > 0) {
                nums[i] = 1;
                oneCount--;
            } else {
                nums[i] = 2;
            }
        }
    }
}

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zero_count, one_count, two_count = 0, 0, 0
        for num in nums:
            if num == 0:
                zero_count += 1
            elif num == 1:
                one_count += 1
            else:
                two_count += 1
        for i in range(len(nums)):
            if zero_count > 0:
                nums[i] = 0
                zero_count -= 1
            elif one_count > 0:
                nums[i] = 1
                one_count -= 1
            else:
                nums[i] = 2

class Solution {
    public void sortColors(int[] nums) {
      // 分别定义3个指针
        int left = 0, current = 0, right = nums.length - 1;
        while (current <= right) {
            int num = nums[current];
            // 如果num = 0则交换left, current
            if (num == 0) {
                swap(nums, left, current);
                left++;
                current++;
            // 如果num = 2则交换current, right
            } else if (num == 2) {
                swap(nums, current, right);
                right--;
            // 否则为1
            } else {
                current++;
            }
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left, current, right = 0, 0, len(nums) - 1
        while current <= right:
            num = nums[current]
            if num == 0:
              // python语法支持这样的交换值逻辑，所以并不需要定义交换值方法
                nums[left], nums[current] = nums[current], nums[left]
                left += 1
                current += 1
            elif num == 2:
                nums[current], nums[right] = nums[right], nums[current]
                right -= 1
            else:
                current += 1