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]

分析思路

通过第一次遍历记录0、1、2对应的个数（桶排序），然后第二次遍历将0、1、2进行填入即可。

代码实现

C++版本

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int a[3] = {0}; //统计0 1 2出现的次数
        for (int i=0; i<nums.size(); ++i) {
            ++a[nums[i]];
        }

        int base = 0;
        int digit = 0;

        #外层循环表示的是几个数
        for (int i=0; i<3; ++i) {
            int offset = 0;

            for (int j=0; j<a[i]; ++j) {
                nums[base + offset] = digit;
                ++offset;
            }

            base += offset;
            ++digit;
        }

    }
};

Java版本

class Solution {
    public void sortColors(int[] nums) {
        int[] a = new int[3];
        for(int i=0; i<nums.length; ++i) {
            ++a[nums[i]];
        }

        int base = 0;
        int digit = 0;

        for(int i=0; i<3; ++i) {
            int offset = 0;
            for (int j=0; j<a[i]; ++j) {
                nums[base + offset] = digit;
                ++offset;
            }

            base += offset;
            ++digit;
        }
    }
}

Python2版本

class Solution(object):
    def sortColors(self, nums):
        num_counts = [0, 0, 0]

        for i in nums:
            num_counts[i] += 1

        base = 0
        digit = 0

        for i in range(0, 3):
            offset = 0
            for j in range(0, num_counts[i]):
                nums[base + offset] = digit
                offset += 1

            base += offset
            digit += 1