您當(dāng)前位置：首頁(yè) > php開(kāi)源 > php教程 > 【一天一道LeetCode】#75. Sort Colors

【一天一道LeetCode】#75. Sort Colors

來(lái)源：程序員人生發(fā)布時(shí)間：2016-06-15 14:34:38 閱讀次數(shù)：2675次

1天1道LeetCode

本系列文章已全部上傳至我的github，地址：ZeeCoder‘s Github
歡迎大家關(guān)注我的新浪微博，我的新浪微博
歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處

（1）題目

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?

（2）解題

題目大意：數(shù)組包括0,1,2，依照大小排列這些數(shù)字。

1、最簡(jiǎn)單的方法

利用STL的sort1句話就解決了。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        sort(nums.begin(),nums.end());
    }
};

2、兩個(gè)指針

算法思想很簡(jiǎn)單，把所有的0交換到隊(duì)首，把所有的1交換到隊(duì)尾

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int start = 0;
        int end = nums.size()-1;
        for(int i = 0 ; i<nums.size();i++)//把0交換到前面
        {
            if(nums[i]==0) {
                if(i!=start) swap(nums[i],nums[start]);
                start++;
            }
        }
        for(int i = nums.size()-1 ; i>=start ;i--)//把2交換到尾部
        {
            if(nums[i]==2){
                if(i!=end) swap(nums[i],nums[end]);
                end--;
            }
        }
    }
};

3、兩個(gè)指針優(yōu)化版

保持3個(gè)指針i、j和k，從0~i表示1，i+1~j表示1，k~nums.size()表示2
代碼也比較簡(jiǎn)單：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int i = 0, j = i, k = nums.size() - 1;
        while(j <= k){
            if(nums[j] == 0) swap(nums[i++], nums[j++]);//0交換到前面
            else if(nums[j] == 1) j++;//1保持不動(dòng)
            else swap(nums[k--], nums[j]);//2交換到尾部
        }
    }
};