颜色分类

题目链接

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例:

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

思路

解法一：

使用单指针进行两次遍历，第一次交换0的位置，第二次交换1的位置

  1. 第一次遍历，若为0， 则交换位置；
  2. 第二次遍历，若为1， 则交换位置。
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        index = 0
        for i in range(n):
            if nums[i] == 0:
                nums[index], nums[i] = nums[i], nums[index]
                index += 1
        for j in range(index, n):
            if nums[j] == 1:
                nums[index], nums[j] = nums[j], nums[index]
                index += 1

解法二：

使用双指针进行1次遍历

  1. 左右指针分别指向开头和结尾
  2. 从左到右遍历数组，若nums[i]为2，则与右指针指向的元素进行循环交换（这里不能是if，考虑到[2, 1, 2]特殊情况）
  3. 若nums[i]为0，则与左指针指向的元素进行交换
    def sortColors1(self, nums: List[int]) -> None:
        n = len(nums)
        left, right = 0, n - 1
        i = 0
        while i <= right:
            # 这里不能是if nums[i] == 2,考虑到特殊情况nums = [2,1,2]
            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