分析

• 本题的考点：三路快排。

• 本题需要使用三个指针i、j、k，初始i=0, j=0, k=nums.size()-1；其中[0, j-1]存储0，[j, i-1]存储1，[k+1, nums.size()-1]存储2，刚开始三个区间都为空区间，满足定义。

• 具体分为三种情况，如下图：

代码

• C++

class Solution {
public:
    void sortColors(vector<int>& nums) {

        for (int i = 0, j = 0, k = nums.size() - 1; i <= k; ) {
            if (nums[i] == 0) swap(nums[i++], nums[j++]);
            else if (nums[i] == 2) swap(nums[i], nums[k--]);
            else i++;
        }
    }
};

• Java

class Solution {
    public void sortColors(int[] nums) {

        for (int i = 0, j = 0, k = nums.length - 1; i <= k; ) {
            if (nums[i] == 0) swap(nums, i++, j++);
            else if (nums[i] ==2) swap(nums, i, k--);
            else i++;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为数组长度。

• 空间复杂度：$O(1)$。