Leetcode[75] Sort Colors

1. Time O(n), Space O(n)

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int r = 0, w = 0, b = 0;
        for(int i: nums) {
            if(i == 0) r++;
            else if (i == 1) w++;
            else b++;
        }
        vector<int> sorted;
        for(int i = 0; i < r; i++) {
            sorted.push_back(0);
        }
        for(int i = 0; i < w; i++) {
            sorted.push_back(1);
        }
        for(int i = 0; i < b; i++) {
            sorted.push_back(2);
        }
        nums.swap(sorted);
    }
};

2. O(n) O(1)

class Solution {
public:
    void sortColors(vector<int>& nums) {
        if(nums.size() <= 1) return;
        int r = 0, w = 0, b = nums.size()-1;
        while(w <= b) {
            if(nums[w] == 0) {
                nums[w] = nums[r];
                nums[r] = 0;
                w++;
                r++;
            } else if(nums[w] == 1) {
                w++;
            } else {
                nums[w] = nums[b];
                nums[b] = 2;
                b--;
            }
        }
    }
};