75. Sort Colors

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

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.

click to show follow up.

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?

Thoughts

对只由0，1和2构成的数组排序。和bucket sort思想类似，看作有0，1和2三个bucket，分别由两个指针隔开，首指针前的都是排好的0，尾指针后的都是排好的2，0,...,0,1(j),...,1, x(i),x,x(k), 2,2,...,2，然后遍历让让i指向待排元素，j和k分别指向当前已经就位的下一个位置。对nums[i]作判断，当nums[i]==1，未知边界指针i++；当nums[i]==0, 把它和j swap，++j。当nums[i]==2, 和right swap，--k。由于交换回i的x值未知，因此不能直接i++，应继续循环以检查i的新值是多少。

Code

/*
 * @lc app=leetcode id=75 lang=cpp
 *
 * [75] Sort Colors
 */

// @lc code=start
class Solution {
public:
    void sortColors(vector<int>& nums) {
        const int N = nums.size();
        for (int i = 0, j = 0, k = N - 1; i <= k;) {
            if (nums[i] == 0 && j < i) swap(nums[i], nums[j++]);
            else if (nums[i] == 2 && k > i) swap(nums[i], nums[k--]);
            else ++i;
        }
    }
};
// @lc code=end

/*
 * @lc app=leetcode id=75 lang=cpp
 *
 * [75] Sort Colors
 *
 * https://leetcode.com/problems/sort-colors/description/
 *
 * algorithms
 * Medium (43.05%)
 * Likes:    1897
 * Dislikes: 168
 * Total Accepted:    349.1K
 * Total Submissions: 810.6K
 * Testcase Example:  '[2,0,2,1,1,0]'
 *
 * 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?
 * 
 * 
 */
class Solution {
public:
    void sortColors(vector<int>& nums) {
        const int N = nums.size();
        int l = 0, r = N - 1, i = 0;
        while (i <= r) {
            if (nums[i] == 0) {
                swap(nums[i], nums[l++]);
                if (i < l) ++i; // if 可以去掉让i直接++，但不好理解
            }
            else if (nums[i] == 1) ++i;
            else swap(nums[i], nums[r--]);
        }
    }
};

Analysis

Errors:

1. i = 1初始必须为0，如[2,1]

2. i < right，必须是i<=right, 如[1,0], 由于nums[i] == 1了，紧接着又i < right，不执行了

时间复杂度O(n), 空间O(1)

当有k种颜色需要排序

这时就无法1 pass做出来了。但有一个general的模板解决这类问题，即bucket sort.

依序每次把nums中和i相等的换到前面的相应位置。

以下是别人写的代码

public class Solution {
    public void sortColors(int[] nums) {
        int[] cand = {0, 1, 2};
        int start=0;
        for(int i=0;i<3;i++){
            while(start<nums.length && nums[start]==cand[i]) start++;
            for(int j=start;j<nums.length;j++){
                if(nums[j]==cand[i]){
                    swap(nums, j, start++);
                }
            }
        }
        return;
    }
    public void swap(int[] nums, int a, int b){
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}

时间复杂度O(nk)