# 75. Sort Colors

## 1.問題

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LIBwfupKxFlkXf4xL8b%2F-LIBxdZ4Of9C-0E_NuTl%2F2018072401.jpg?alt=media\&token=9124063d-6a10-4b8d-8df2-53f156622480)

## 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;
    } 
};
```