75. Sort Colors

1.問題

• 給予n個物件, in-place sort讓同樣顏色的排在一起

2.想法

• 提問:

• function header, parameter

• test input

• 說明想法

  • 1.用一個vector記數0 ~ 2出現的次數, 再重填回去

  • 2.用頭尾指針標示下一個red, blue應該交換的位置

    • 2被0換走後, 有可能是0(0不能在中間), 需要再次檢查

    • 0被換走, 只會是最大的

• 測試計算複雜度

3.程式碼

• 方法1

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

• 方法2

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