075.md

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.

题意：一个数组只有0 1 2 分别代表红白蓝 ， 将该数组排序。

思路

1.使用三个变量red，white，blue计数红白蓝，最后nums前red个元素赋值为0，前white赋值为1，前blue赋值为2.

2.使用一个索引previous_first_blue初始化为nums的最后一个索引位置，表示指向蓝色的前一个元素的索引。

初始first_white=0表示指向第一个white色的位置的索引。初始cur=0为指向当前扫描的索引用来遍历。

遍历cur<=previous_first_blue。

如果nums[cur]==1，然后++cur.

如果nums[cur]==2. swap(nums[cur],nums[previous_first_blue]); 然后previous_first_blue--。不用改变cur因为交换过来给cur下标的元素是没有检测过的。

如果nums[cur]==0. swap(nums[cur],nums[first_white]); 然后cur++处理下一个元素;first_white++保持first_white指向白色的第一个元素;first_white也是 红色的最后一个元素的下一个元素。

代码

straight forward solution :

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red=0,white=0,blue=0;
        int sz = nums.size();
        for(int i=0;i<sz;++i){
            if(nums[i]==0){
                red++;
            }else if(nums[i]==1){
                white++;
            }else{
                blue++;
            }
        }
        
        for(int i=0;i<red;++i) nums[i] = 0;
        for(int i=0;i<white;++i) nums[red+i] = 1;
        for(int i=0;i<blue;++i) nums[red+white+i] = 2;
    }
};

解法2：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int previous_first_blue = nums.size()-1;
        int first_white = 0;
        int cur = 0;
        while(cur<=previous_first_blue){
            if(nums[cur]==0){
                swap(nums[cur++],nums[first_white++]);
            }else if(nums[cur]==2){
                swap(nums[cur],nums[previous_first_blue--]);
            }else{
                cur++;
            }
        }
    }
};