75. 颜色分类

本题来自 LeetCode：75. 颜色分类^[1]

题目描述

给定一个包含红色、白色和蓝色，一共 n个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、  1和 2分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:

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

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

1. 两趟扫描

题目分析

根据进阶的提示，可以采用两趟扫描

第一趟扫描，先统计三种颜色的个数；

第二趟扫描，按照三种颜色的个数，按`0、1、2`的顺序，填充原数组；

题目解答

class Solution {
    public void sortColors(int[] nums) {
        int counts[] = new int[3];
        // 第一趟扫描，先统计三种颜色的个数
        for(int i = 0; i  nums.length; i ++) {
            counts[nums[i]] = counts[nums[i]] + 1;
        }
        // 按照三种颜色的个数重写原数组
        int index = 0;
        for(int i = 0; i  counts.length; i ++) {
            for(int j = 0; j  counts[i]; j ++) {
                nums[index ++] = i;
            }
        }
    }
}

复杂度分析：
时间复杂度： O(n) ，两趟扫描
空间复杂度： O(1)

2. 一趟扫描

题目分析

一趟扫描，需要边扫描，边排序。

采用两个指针`left`、`right`，`left`指针记录未排序的起始下标、`right`记录未排序的结束下标。

然后迭代这个区间，要睡觉了，直接看解答吧～～～

题目解答

class Solution {
    public static final int RED = 0;
    public static final int WHITE = 1;
    public static final int BLUE = 2;

    public void sortColors(int[] nums) {
        // 记录未排序的起始下标
        int left = 0;
        // 记录未排序的结束下标
        int right = nums.length - 1;

        for(int i = left; i = right; i ++) {
            // 若是蓝色
            if(nums[i] == BLUE) {
                // 则先从右边找到第一个不是蓝色的元素下标
                while(right = i && nums[right] == BLUE) {
                    right --;
                }
                // 若已有序，则结束
                if(right  i) {
                    break;
                }
                // 将位置i的蓝色和right的元素（红色or白色，这里不区分，下一步区分）交换
                swap(nums, i, right --);
            }
            // 若i位置的当前值为红色，则移到前面去
            if(nums[i] == RED) {
                swap(nums, i, left ++);
            }
            if(nums[i] == WHITE) {
                //do nothing
            }
        }
    }
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

复杂度分析：
时间复杂度： O(n)，一趟扫描
空间复杂度： O(1)

参考资料

75. 颜色分类: https://leetcode-cn.com/problems/sort-colors

原文始发于微信公众号（xiaogan的技术博客）：