LeetCode75. Sort Colors（模拟）

Medium
Accepted：283,496
Submissions：691,131

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]

Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with a one-pass algorithm using only constant space?

链接

https://leetcode.com/problems/sort-colors/

题意

给定一个含有n个元素的数组，其中只包含0、1、2三种数字，对齐进行排序。不允许使用函数库的排序算法。

题解

因为只包含0，1，2三种数字，所以怎么操作都可以。我的做法是遍历一遍分别统计下0、1、2三种数字的数量然后挨个赋值。时间复杂度$O(n)$，空间复杂度是$O(k)=O(1)$，k为元素的取值范围。

代码

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Sort Colors.
Memory Usage: 761.9 KB, less than 68.11% of C++ online submissions for Sort Colors.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int cntColor[3] = {0};
        // 先统计
        for (int i = 0; i < len; ++i)
            cntColor[nums[i]]++;
        int cntNum = 0;
        // 后放回
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < cntColor[i]; ++j)
                nums[cntNum++] = i;
    }
};

有点计数排序的感觉哈。

还有一种做法的思想是三路快速排序，具体见代码。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int zero = -1; // nums[0, zero] == 0
        int two = nums.size(); // nums[two, n-1] == 2
        for (int i = 0; i < two; )
        {
            if (nums[i] == 1)
                ++i;
            else if (nums[i] == 2)
                swap(nums[i], nums[--two]);
            else if (nums[i] == 0)
                swap(nums[i++], nums[++zero]);
        }
    }
};

The end.
2019年2月2日星期六