[LeetCode]75.Sort Colors

【题目连接】

75.Sort Colors

【题目】

Given an array withnobjects 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?

【分析】

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.

这是我们首先会想到的。可是题目要求我们不能这样。

【代码】

    /**------------------------------------
    *   日期：2015-02-02
    *   作者：SJF0115
    *   题目: 75.Sort Colors
    *   网址：https://oj.leetcode.com/problems/sort-colors/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        void sortColors(int A[], int n) {
            if(n <= 1){
                return;
            }//if
            // 统计个数
            int red = 0,white = 0,blue = 0;
            for(int i = 0;i < n;++i){
                if(A[i] == 0){
                    ++red;
                }//if
                else if(A[i] == 1){
                    ++white;
                }//else
                else{
                    ++blue;
                }//else
            }//for
            // 重新布局
            for(int i = 0;i < n;++i){
                if(red > 0){
                    A[i] = 0;
                    --red;
                }//if
                else if(white > 0){
                    A[i] = 1;
                    --white;
                }//else
                else{
                    A[i] = 2;
                }
            }//for
        }
    };

    int main(){
        Solution s;
        int A[] = {0,0,1,0,2,0,1,2};
        s.sortColors(A,8);
        for(int i = 0;i < 8;++i){
            cout<<A[i]<<endl;
        }//for
        // 输出
        return 0;
    }

【思路二】

用三个变量记录red,white,blue的下标位置。起始下标都为-1

如果A[i] == 0 ，插入red对white blue有影响，blue先整体向后移动一位，white再整体向后移动一位，如果不移动，前面插入的数据就会覆盖已有的。

如果A[i] == 1，插入white对blue有影响，blue整体向后移动一位。

A[i] == 2，直接插入blue

【代码二】

    /**------------------------------------
    *   日期：2015-02-03
    *   作者：SJF0115
    *   题目: 75.Sort Colors
    *   网址：https://oj.leetcode.com/problems/sort-colors/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        void sortColors(int A[], int n) {
            if(n <= 1){
                return;
            }//if
            int red = -1,white = -1,blue = -1;
            for(int i = 0;i < n;++i){
                // 插入red对white blue有影响
                if(A[i] == 0){
                    // blue整体向后移动一位
                    A[++blue] = 2;
                    // white整体向后移动一位
                    A[++white] = 1;
                    // 插入red
                    A[++red] = 0;
                }//if
                // 插入white blue受到影响
                else if(A[i] == 1){
                    // blue整体向后移动一位
                    A[++blue] = 2;
                    // 插入white
                    A[++white] = 1;
                }//else
                // 插入blue对其他没有影响
                else{
                    // 插入blue
                    A[++blue] = 2;
                }//else
            }//for
        }
    };

    int main(){
        Solution s;
        int A[] = {0,0,1,0,2,0,1,2};
        s.sortColors(A,8);
        for(int i = 0;i < 8;++i){
            cout<<A[i]<<endl;
        }//for
        // 输出
        return 0;
    }

【思路三】

冒泡排序

class Solution {
public:
    void sortColors(int A[], int n) {
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(A[j]>A[j+1]){
                    int tmp=A[j];
                    A[j]=A[j+1];
                    A[j+1]=tmp;
                }
            }
        }
    }
};

【思路四】

我们可以把数组分成三部分，前部（全部是0），中部（全部是1）和后部（全部是2）三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。

将前部和后部各排在数组的前边和后边，中部自然就排好了。

设置两个指针begin指向前部的末尾的下一个元素（刚开始默认前部无0，所以指向第一个位置），end指向后部开头的前一个位置（刚开始默认后部无2，所以指向最后一个位置），然后设置一个遍历指针current，从头开始进行遍历。

（1）若遍历到的位置为1，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前移动一个位置。

（2）若遍历到的位置为0，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前移动一个位置，begin也向前移动一个位置（表示前边的已经都排好了）。

（3）若遍历到的位置为2，则说明它一定属于后部，于是就和end位置进行交换，由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。而同1），end向前移动一个位置。

【代码四】

    /**------------------------------------
    *   日期：2015-02-04
    *   作者：SJF0115
    *   题目: 75.Sort Colors
    *   网址：https://oj.leetcode.com/problems/sort-colors/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
   class Solution {
    public:
        void sortColors(int A[], int n) {
            int begin = 0,end = n-1,cur = 0;
            while(cur <= end){
                if(A[cur] == 0){
                    swap(A[begin],A[cur]);
                    // 指向排序0末尾的下一个位置
                    ++begin;
                    // 向前遍历
                    ++cur;
                }//if
                else if(A[cur] == 1){
                    ++cur;
                }//else
                else{
                    swap(A[end],A[cur]);
                    // 指向排序2开头的前一个位置
                    --end;
                }//else
            }//for
        }
    };

详细参考：[算法系列之十一]荷兰国旗问题