75. Sort Colors.md

75. Sort Colors

思路

将一个只包含三种元素的数组进行排序，要求只能遍历一遍，不能使用桶排序（需要两次遍历）。
其实这题就是学习数据结构快排时可能遇到的"荷兰国旗问题"，可以用快排类似的partition的方法求解。
定义两个指针right_0和left_2初始分别为-1和nums.size()。始终满足right_0及其左边的元素全为0、left_2及其右边的元素全为2。 从前往后遍历数组，将0放在位置right_0 + 1（通过swap完成，下同）并更新right_0, 将2放在位置left_2 - 1并更新left_2，遍历完成后即所有的0都在左边，所有的2都在右边，中间全为1。

注意：

代码中最后else那里不更新i!!! 因为可能交换后nums[i]=0，需要在下一次循环中再次交换

时间复杂度O(n)，空间复杂度O(1)

C++

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int i = 0, right_0 = -1,  left_2 = len;
        while(i < left_2){
            if(nums[i] == 0) swap(nums[i++], nums[++right_0]); 
            else if(nums[i] == 1) i++;
            else swap(nums[i], nums[--left_2]); // 注意这里不更新i, 因为可能交换后nums[i]=0，需要在下一次循环中再次交换
        }
    }
};