# 75 - Sort Colors

解法一 - Three pointers

這題是 Dijkstra 提出的，解法頗為聰明，請見下圖：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0 = 0, cur = 0;
        int p2 = nums.size()-1;

        while(cur <= p2) {
            if(nums[cur] == 0) swap(nums[p0++], nums[cur++]);
            else if(nums[cur] == 2) swap(nums[p2--], nums[cur]);
            else cur++;
        }
    }
};

這題的一個直覺 follow-up 就是，如果今天 array 裡面的東西不是 0 1 2，而是更廣義的三種不同東西，那就不會這麼簡單，可以看看這個影片增加一些體會。