【经典算法题】颜色分类

题目描述：Leetcode 0075 颜色分类

分析

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

• 本题需要使用三个指针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& 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;
    }
}

• Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = 0; j = 0; k = len(nums) - 1
        while i <= k:
            if nums[i] == 0:
                nums[j], nums[i] = nums[i], nums[j]
                i += 1; j += 1
            elif nums[i] == 2:
                nums[i], nums[k] = nums[k], nums[i]
                k -= 1
            else:
                i += 1

时空复杂度分析

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

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