75. 颜色分类（中等）

1. 题目描述

题目中转：75. 颜色分类

2.详细题解

方法一：桶排序

    只有三类颜色，按照指定颜色顺序排列，且原地排序，直使用桶排序算法。对于本题，先统计各颜色出现的频率，再按照指定颜色顺序，再原数组内存入相应的颜色，具体算法如下：

• Step1：初始化：颜色的顺序已经确定，直接建桶，由于各颜色使用数字$0,1,2$表示，桶数据结构为数组，索引$i(i<3)$处的数字即为该颜色出现的频率；原地数组排序的初始索引为$j=0$；
• Step2：遍历数组，根据颜色放入对应桶中，算法时间复杂度为$O(n)$；
• Step3：从左至右遍历桶，桶的索引为$i$，值为$k$，则在原数组$[j:j+k)$中放入值$i$;
• Step4：遍历结束，程序结束。

方法二：双指针

    只有三类颜色，颜色$0$和$2$分别放入开头位置和结尾位置，因此可以使用双指针分别指向颜色$0$和颜色$1$，从左至右遍历数组，如果遇到颜色$0$，则与左指针指向的值交换位置，如果遇到颜色$2$，则与右指针指向的值交换位置。当遇到颜色$1$时则不交换位置。
  算法需要注意的细节是，对于左指针指向的值，一定不为颜色$2$（因为左指针指向的位置<=遍历位置，如果能为$2$，已经交换到尾部去了），对于右指针指向的值，可能为任意值，因此与遍历位置交换值后，该遍历位置还需要进行判断，并不能遍历下一个位置，否则会出现错误。
  具体算法如下：

• Step1：初始化：两个指针 $left$ 和 $right$，分别指向数组的起始和结束位置；
• Step2：遍历指针未$i$，初始指向起始位置；
• Step3：如果 $nums[i]==2$且$i<=right$，则交换$i$和$right$位置的值，$right$指针向左移动一位，即$right--$;
• Step4：重复步骤Step3，直至条件不成立；
• Step5：如果$nums[i]==0$，则交换$i$与$left$位置的值，$left$指针向右移动一位，即$left++$;
• Step6：遍历指针$i$向右移动一位，$i++$;
• Step7：条件$i<=right$成立，则重复步骤Step3_Step6，否则到步骤Step8；
• Step8：程序结束。

3.代码实现

3.1 Python

方法一：桶排序

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        bucket = [0, 0, 0]
        for num in nums:
            bucket[num] += 1
        j = 0
        for i in range(3):
            for _ in range(bucket[i]):
                nums[j] = i
                j += 1

方法二：双指针

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left, right = 0, len(nums) - 1
        i = 0
        while i <= right:
            while i <= right and nums[i] == 2:
                nums[i], nums[right] = nums[right], nums[i]
                right -= 1
            if nums[i] == 0:
                nums[i], nums[left] = nums[left], nums[i]
                left += 1
            i += 1

3.2 Java

方法一：桶排序

class Solution {
    public void sortColors(int[] nums) {
        int[] bucket = {0, 0, 0};
        for (int num: nums){
            bucket[num]++;
        }
        int j = 0;
        for (int i=0; i < 3; i++){
            for (int z=0; z < bucket[i]; z++){
                nums[j++] = i;
            }
        }
    }
}

方法二：双指针

class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int i = 0;
        while (i <= right){
            while (i <= right && nums[i] == 2){
                int tmp = nums[i];
                nums[i] = nums[right];
                nums[right--] = tmp;
            }
            if (nums[i] == 0){
                int tmp = nums[i];
                nums[i] = nums[left];
                nums[left++] = tmp;
            }
            i++;
        }
    }
}

  执行用时不必过于纠结，对比可以发现，对于python和java完全相同的编写，java的时间一般是优于python的；至于编写的代码的执行用时击败多少对手，执行用时和网络环境、当前提交代码人数等均有关系，可以尝试完全相同的代码多次执行用时也不是完全相同，只要确保自己代码的算法时间复杂度满足相应要求即可，也可以通过点击分布图查看其它coder的code。