0075-颜色分类

题目链接

题目描述

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例

示例1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

提示

• n == nums.length
• 1 <= n <= 300

• nums[i] 为 0、1 或 2

  进阶

• 你可以不使用代码库中的排序函数来解决这道题吗？

• 你能想出一个仅使用常数空间的一趟扫描算法吗

  思路

  思路1：排序

  直接进行排序。

  思路2：计数

  统计三个数字出现的次数，然后对 nums 重新赋值。

  思路3：单指针

  维护一个指针 p ，它左边为已经排序好的数字，从头遍历数组，将值为 0 的数与 nums[p] 交换，最终得到的数组中，0全在 p 的左边；
  然后进行第二次遍历，将值为 1 的数与 nums[p] 交换，得到最终结果。

  思路4：双指针

  我们目的是让 0 集中到数组的左边，2 集中到数组的右边，中间为 1 ，因此可以考虑双指针。
  设两个指针 letf = 0 和 right = n - 1 ，从头遍历数组：

1. nums[i] == 0，与 nums[left] 交换；我们易知 left <= i ，因此 left 所处的位置是已经排序好的，此交换不会产生问题。
2. nums[i] == 2，与 nums[right] 交换；如果 nums[right] == 2 ，则交换后 nums[i] == 2 ，若直接遍历下一元素就会出问题，因此此时应该继续交换， 直至 nums[right] != 2 停止。``
3. nums[i] == 1，不做处理。

注意：因为情况2可能会交换出 nums[i] == 0 ，因此情况2要在情况1之前处理。
当 i > right 时停止遍历。

题解

思路4：双指针

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

复杂度分析

• 时间复杂度：
• 空间复杂度：