leetcode-75. Sort Colors 顔色分類

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?

給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顔色的元素相鄰，并按照紅色、白色、藍色順序排列。 此題中，我們使用整數 0、 1 和 2 分别表示紅色、白色和藍色。 注意: 不能使用代碼庫中的排序函數來解決這道題。 示例: 輸入: [2,0,2,1,1,0] 輸出: [0,0,1,1,2,2] 進階： 一個直覺的解決方案是使用計數排序的兩趟掃描算法。 首先，疊代計算出0、1 和 2 元素的個數，然後按照0、1、2的排序，重寫目前數組。 你能想出一個僅使用常數空間的一趟掃描算法嗎？

思路：

第一種：題目中說的，疊代算出0,1,2分别出現了 多少次，然後按照0,1,2分别出現的 次數複制到原數組 中

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int arr[3]={0},k=0;
        for(int i=0;i<nums.size();++i)
            arr[nums[i]]++;
        for(int i=0;i<3;++i)
            for(int j=0;j<arr[i];++j)
                nums[k++]=i;
    }
};
           

第二種：因為是紅白藍排序，是以使用兩個指針，red指針從前往後，blue指針從後往前。若遇到為0的，red指針位置與其交換，若遇到為2的，blue指針與其交換，若遇到為1的，不用管。例如：[2,0,2,1,1,0]，首先red 指針指向0位置的2，blue指針指向5 位置的0

[2,0,2,1,1,0]    

[0,0,2,1,1,2]     從前往後周遊為2，blue位置與其交換，

[0,0,2,1,1,2]    

[0,0,1,1,2,2]     周遊為2，與blue位置交換

[0,0,1,1,2,2]

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int red=0, blue=nums.size()-1;
        for(int i=0;i<=blue;++i)   //注意這裡i<=blue
        {
            if(nums[i]==0) swap(nums[i],nums[red++]);
            else if(nums[i]==2) swap(nums[i--],nums[blue--]);  //記得交換之後i--,從i前一個位置開始
        }
    }
};