> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/75.-sort-colors-medium.md).

# 75. Sort Colors

## 1.問題

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

![](/files/-LIBxdZ4Of9C-0E_NuTl)

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