Leetcode 75：Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

说人话：

一个数组中只有 0，1，2 这三种情况，对数组进行原地排序。

几个要点：

• 原地排序
• 值只有3种可能

[法1] 采用任何一种常用的排序算法

因为 0，1，2 是可以比较大小的，我们这里我们采用任何一种排序算法都是可以解出这个题目的。

[法2] 基数排序

思路

因为这道题非常特殊，值就只有 0，1，2 这三种情况，所以我们可以：

• 遍历 nums 数组，分别统计 0，1，2 的个数；
• 根据 0，1，2 的个数更新 nums

这其实就是基数排序的思想。

代码

class Solution {
    public void sortColors(int[] nums) {

        //记录0，1，2 的个数
        int[] count = new int[3];

        //遍历 nums，得到 0，1，2 的个数
        for(int i = 0;i<nums.length;i++){
            if(nums[i] == 0){
                count[0] ++;
            }else if(nums[i] == 1){
                count[1] ++;
            }else if(nums[i] == 2){
                count[2] ++;
            }
        }

        //刷新 nums
        for(int i=0;i<count[0];i++){
            nums[i] = 0;
        }
        for(int i=0;i<count[1];i++){
            nums[i+count[0]] = 1;
        }
        for(int i=0;i<count[2];i++){
            nums[i+count[0]+count[1]] = 2;
        }
    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：因为需要记录每种元素的个数，所以需要 O(k)

改进思路

本思路我们总共扫描了两遍数组才完成了排序，那么有没有可能只扫描一遍数组就完成排序呢？那就需要用到下面说的三路快排了。

[法3] 三路快排

思路

所谓三路快排，就选定一个基准v，将数组划分为 <v，==v，>v 这三个部分，然后再对这三个部分进行递归三路快排，直至划分不了。

因为本题的值只有3种情况，所以可以直接以 1 为基准，划分出 <1，==1，>1 的情况，就完成了本题的要求。

整体思路如下：

• 建立 3 个索引 zero、i、two
• 保证 [0…zero] 都为0
• 保证 [two…n-1] 都为2
• i 遍历数组，在遍历数组的同时要同时保证 [zero…i-1] 都为1

代码

class Solution {
    public void sortColors(int[] nums) {
        //[0...zero] 都为0
        int zero = -1;
        //[two...n-1] 都为2
        int two = nums.length;
        //[zero+1...i-1] 都为1
        for(int i=0;i<two;){    //因为[two...n-1]都已经确定为2了，所以当 i 撞到 two 的时候就可以停下了
            //如果nums[i]为1，则i继续往后移就可以了
            if(nums[i] == 1){
                i++;
            }
            //如果nums[i]为0
            else if(nums[i] == 0){
                //则将nums[i]和nums[zero+1]进行交换
                int temp = nums[i];
                nums[i] = nums[zero+1];
                nums[zero+1] = temp;
                //然后zero++，保证 [0...zero]都为0，且[zero+1....i-1]都为1
                zero++;
                //因为原来的nums[zero+1]就是1，所以这个时候nums[i]已经确定为1了，i++，继续往后
                i++;
            }
            //如果nums[i]为2
            else if(nums[i] == 2){
                //则将nums[two-1]（不确定）和nums[i] 进行交换
                int temp = nums[i];
                nums[i] = nums[two-1];
                nums[two-1] = temp;
                //two--，保证[two....n-1] 都为2
                two--;
                //这里不需要i++,因为交换后nums[i]的值是原来的nums[two-1]，是不确定的
            }
        }

    }
}

提交结果

代码分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)