题目

解答

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

        while(cur < r) {
            if(nums[cur] < 1) {
                std::swap(nums[++l], nums[cur++]);
            } else if(nums[cur] > 1) {
                std::swap(nums[cur], nums[--r]);
            } else 
                ++cur;
        }
    }
};

算法思想

这是一道经典的"荷兰国旗"问题，本质上就是根据三种性质来将当前数据划分成三个部分。本题目的三个性质分别是小于 1，等于 1 和大于 1。因此，我们需要在遍历的过程中对数据进行划分，具体看下面图解。

初始情况，l = -1，cur = 0，r = 6，我们需要在 cur 遍历的过程中始终保持 [0, l] 满足小于 1，[r, 5] 满足大于 1。

当 cur = 0，arr[cur] > 1 时，需要与 arr[r-1] 的数进行交换，并且 --r；

当 cur = 0，arr[cur] < 1 时，需要与 arr[l+1] 的数进行交换，同时 l++，cur++；

当 cur = 1，arr[cur] < 1 时，需要与 arr[l+1] 的数进行交换，同时 l++，cur++；

当 cur = 2，arr[cur] > 1 时，需要与 arr[r-1] 的数进行交换，并且 --r；

当 cur = 2，arr[cur] = 1 时，直接 ++cur。至此，后续我们不再重复，当 cur = r 的时候，循环结束。

这里有个关键点需要注意一下：

• 为什么 l++ 的时候，cur++，而 r-- 的时候，cur 不需要减 1？

这是因为，我们在遍历的过程中，会保证 l 到 cur 之间的数据要么不存在，要么一定等于 1，因此，当 arr[cur] < 1，与 arr[l+1] 的数据进行交换的时候，我们可以放心的 cur + 1，但是 arr[r-1] 的数字我们无法保证。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)