Leetcode 75: sort colors // sort color II (lintcode)

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.
这题是rainbow sort，用挡板法线性shuffle, 完成排序。
要注意的是挡板的数量，如果是3个区域，那么需要3个挡板，3个挡板4个区域，i, j, k, 0-i: 0, i-j: 1, j-k: explore , k-size-1: 2, 如果是2 个区域，那么需要2个挡板，在用挡板做题的时候要考虑挡板数量以及怎么使用。 

结合后面sort k color的题目，觉得sort color这个题目更通用的理解方法还是 挡板区域法 + moving pointer这种比较好理解， 如果是sort 2 color的话， 就是 1 board + 1 moving pointer index， 如果是 sort 3 color， 就是 2 board + 1 moving pointer index，sort k color, 在 sort２color的基础上， 移动 的pointer来控制区间中元素的移动。  

class Solution {
public:
    void sortColors(vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return;
        //3 boards 4 intervals
        int i = 0;
        int j = 0;
        int k = nums.size()-1;
        while (j <= k) {
            if (nums[j] == 0) {
                swap(nums[i], nums[j]);
                i++;
                j++;
            } else if (nums[j] == 1) {
                j++;
            } else {
                swap(nums[j], nums[k]);
                k--;
            }
        }
        return;
    }
};

Sort color II

给定一个有n个对象（包括k种不同的颜色，并按照1到k进行编号）的数组，将对象进行分类使相同颜色的对象相邻，并按照1,2，...k的顺序进行排序。

样例

给出colors=[3, 2, 2, 1, 4]，k=4, 你的代码应该在原地操作使得数组变成[1, 2, 2, 3, 4]

sort color 的问题： sort 2 color, sort 3 color， 这些问题都是可以用挡板方法做的， 但是对于sort 4 color的问题，就不能再用这个方法了， 因为4个指针太多，可能之前已经排好序的元素会又被swap出去到不正确的位置上。 这个时候要想到由 2-》k的一般方法有： iteratively use 2-way solution, divide and conquer, 因为已经不能简单地modify 2-way solution了，还是用最稳的方法比较好。 
这个题目里面，可以先按照sort 2 color的问题对k个颜色中的2个排好序，然后再排其他的两个， 可以先把第一位和第二位的元素排好序，然后再往中间排， 

sort 2 color的话用两个指针，下面程序里面是start end，每次可以把left 和 right的两个color sort 好， 此时还剩下中间的那些color没有sort好，而且此时left 和 right指针停留在中间颜色开始和结束的位置， 这个时候只需要再去利用2 -way color sort就可以了。
time complexity O(k/2 * n);
对于奇数的颜色个数，

class Solution{
public:
    /**
     * @param colors: A list of integer
     * @param k: An integer
     * @return: nothing
     */  
    void sortColors2(vector<int> &colors, int k) {
        // write your code here
        int start = -1;
        int end = colors.size();
        for (int round = 1; round * 2 <= k; round++) {
            int leftColor = round;
            int rightColor = k-round+1;
            for (int i = start+1; i < end; i++) {
                if (colors[i] == leftColor) {
                    swap(colors[i], colors[++start]);
                } else if (colors[i] == rightColor) {
                    swap(colors[i], colors[--end]);
                    i--;
                }
            }
        }
        return;
    }
};