leetcode Sort Colors

Given an array with n objects colored red, white or blue, sort them 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.

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 an one-pass algorithm using only constant space?

题目地址：leetcode Sort Colors

题目大意: 一个数组中，0代表红色，1代表白色，2代表蓝色。请按照红-白-蓝色的顺序排好。不能使用sort函数。

思路：

方法1

就三种元素，直接计数排序即可。

C++

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3] = {0};
        for(const int num: nums)
            ++count[num];
        
        for(int i = 0, j = 0; j <= 2; ++j)
            while(count[j]--) nums[i++] = j;
    }
};

Python

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        count = [0] * 3
        for num in nums:
            count[num] += 1
        i = 0
        for j in range(3):
            for _ in range(count[j]):
                nums[i] = j
                i += 1

方法2

交换元素，设l为0结尾+1，r为2的开头-1的位置

于是我们可以用i 遍历，从[0,r]

nums[i] == 0: 交换nums[l] 和nums[i]，l++，i++
nums[i] == 2：交换nums[r]和nums[i]，r--(注意交换后nums[i]可能变为0，因此i不+1)
nums[i] == 1： i++

C++

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

Python

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i, l, r = 0, 0, len(nums) - 1
        while i <= r:
            if nums[i] == 0:
                nums[i], nums[l] = nums[l], nums[i]
                i, l = i + 1, l + 1
            elif nums[i] == 2:
                nums[i], nums[r] = nums[r], nums[i]
                r -= 1
            else:
                i += 1

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/