LeetCode—75—Sort Colors(三路快排思想应用

题目

Given an array 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.

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

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

翻译

给定一个数组，包含n个元素，n个元素被随机标记了三种颜色的一种，红色，白色，蓝色。现在原地排序，使相同颜色的元素相邻，按照红色，白色，蓝色的顺序排列。在这里我们分别用0，1，2。代表三种颜色。

解题思路

通过题意可知，这个数组有其特殊性，特点就是数组只包含三种元素。所以首先提供一种暴力的解法。就是分别统计每个元素在数组中出现了多少次。然后根据元素在数组中出现的次数，将数组重新赋值。
代码如下：

// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 计数排序的思路
// 对整个数组遍历了两遍，第一遍统计各个元素个数，第二遍将数组重新赋值
// 时间复杂度: O(n)
// 空间复杂度: O(k), k为元素的取值范围
public class Solution1 {

    public void sortColors(int[] nums) {

        int[] count = {0, 0, 0};    // 存放0, 1, 2三个元素的频率
        for(int i = 0 ; i < nums.length ; i ++){
            assert nums[i] >= 0 && nums[i] <= 2;
            count[nums[i]] ++;
        }

        int index = 0;
        for(int i = 0 ; i < count[0] ; i ++)
            nums[index++] = 0;
        for(int i = 0 ; i < count[1] ; i ++)
            nums[index++] = 1;
        for(int i = 0 ; i < count[2] ; i ++)
            nums[index++] = 2;
    }
}

优化解法

在这里我们可以采用三路快排的思想，什么是三路快排呢，三路快排就是在数组中选择一个标定点，然后以这个标定点为依据，将数组分为三部分，小于标定点的数据，等于标定点的数据，和大于标定点的数据。然后在小于标定点和大于标定点的区域继续采用三路快排的思想排序，就是一个递归调用的过程。对于本题，因为只有三种元素，所以一次调用就完成了整个排序过程。我们先来看几张图。

无标题.png

在这里我们新定义两个索引zero,two。当我们遍历数组时，将0元素放到[0...zero]区间，将为2的元素放到区间[zero..n-1]中。

1.png
由上图可知，此时我们遍历到第i个元素。第i个元素值为2，我们就将第i个元素的值放到two-1的位置。同时将two-1位置的元素放到i的位置。就是交换这两个位置的元素。因为找出为2的元素增加了一个，所以two要减一。而此时i是不变的，因为交换过来的数据是啥仍然是未知的。同理可以分析出当第i个元素如果是0和1要应该怎么处理。具体情况请看代码。

// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 三路快速排序的思想
// 对整个数组只遍历了一遍
// 时间复杂度: O(n)
// 空间复杂度: O(1)
public class Solution2 {

    public void sortColors(int[] nums) {
   // [0...zero] == 0，初始情况zero为-1，此时区间无效。
   //如果初始值为1,那就是说区间中第一个元素是0，
   //而第一个元素未知，所以这里初始值设为-1；
        int zero = -1;       
        int two = nums.length;  // [two...n-1] == 2,同理初始区间是无效区间
        for(int i = 0 ; i < two ; ){
            if(nums[i] == 1)
                i ++;
            else if (nums[i] == 2)
                swap(nums, i, --two);   //two先自减
            else{ // nums[i] == 0
                assert nums[i] == 0;
                swap(nums, ++zero, i++);    //zero先自增
            }
        }
    }

    private void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i]= nums[j];
        nums[j] = t;
    }
}

更多内容欢迎大家关注

yuandatou