LeetCode75-颜色分类

1. 题目描述

• 来源：力扣（LeetCode）
• 链接：https://leetcode-cn.com/problems/sort-colors
  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

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

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

2. 题解

最朴素的想法自然是直接排序，但是题目要求不能使用库的sort函数，而且进阶要求说明该题的时间复杂度是能够降到O(n)的！🤔所以我直接看了官方题解。（是我太菜了，知道肯定是遍历过程中进行交换，但想了一会没想出来就放弃了！）

2.1 方法一：单指针 + 两次遍历

nums中只有0、1、2三种数值，因此可以遍历两次：

1. 第一次遍历把数字0交换到头部，同时使用一个 计数指针 记录被交换的0的个数（或者视为当前可交换数值位置的标记）（遍历完成之后，即表示在该指针之前的数据已经都是0了，第二次遍历时只需遍历该指针之后的数据）;
2. 第二次遍历时，把数字1交换到头部（数字0之后，即第一次遍历的计数指针之后）。

2.2 方法二：双指针 + 单次遍历

方法一虽然时间复杂度也是O(n)，但是对nums遍历了两次，可以使用双指针进行数值交换使用单次遍历解决该问题。

使用两个指针，ptr0用于控制数字0的交换，表示在ptr0之前的数字都是0；ptr1用于控制数字1的交换，表示在ptr1之前（ptr0及其之后）的数字都是1（遍历开始前ptr0、ptr1均初始化为0）。一般情况下示意图如下:

由上图我们可以看出，ptr0所指位置有可能是已经被交换过的数值1的，因此需要处理这一特殊情况。

数字1需要在所有的数字0之后，因此在进行数据交换时，需要考虑一些特殊情况。

• 遍历过程中，如果当前数值为1，将其交换到ptr1所在位置（值得注意的是，整个遍历过程中，都满足ptr0 <= ptr1）。既然ptr1的位置一定大于等于ptr0，那么在进行数字1的交换时就无需关心数值0，直接交换然后将ptr1右移一位即可，如下图所示。

• 但是如果当前数值为0，进行交换时，则需要考虑ptr1的位置了。存在两种情况：
• • ptr0=ptr1，说明还没有数值1被交换，我们只需要直接交换，然后将ptr0和ptr1都右移一位即可，如图；

• • ptr0<ptr1，说明在数值0后面有一部分连续的数值1。此时交换之后，原本ptr0所指的数值1被交换到了一个错误位置，需要将其再次与ptr1所指数值进行交换（将数值1再次还原到它应该在的位置），此时ptr0和ptr1都进行了一次交换，所以均需要右移一位，如图（可以概括为：数值0的一次交换导致占用了一个数值1的位置，因此需要将这个数值1再次交换到正确的位置）：

3. 代码实现

3.1 方法一

Python实现

# 单指针，记录被移动到头部的数字下标，遍历两次
# 第一次将 0 移动到头部，第二次将 1 移动到头部
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        ptr = 0  # 计数指针，也表征当前可交换位置
        n = len(nums)
        # 把所有的 0 移动到头部，记录头部位置
        for i, num in enumerate(nums):
            if num == 0:
                nums[i], nums[ptr] = nums[ptr], nums[i]
                ptr += 1
            
        # 把剩下的（计数指针之后）数据中所有的 1 移动到头部
        for i in range(ptr, n):
            if nums[i] == 1:
                nums[i], nums[ptr] = nums[ptr], nums[i]
                ptr += 1

3.2 方法二

Python实现

# 双指针，分别用于交换 0 和 1
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        ptr0 = ptr1 = 0
        for i, num in enumerate(nums):
            if num == 1:
                # 把数字 1 移动到头部
                nums[i], nums[ptr1] = nums[ptr1], nums[i]
                ptr1 += 1
            elif num == 0:
                # 把数字 0 移动到头部，此处存在两种情况：
                # 1、数字 0 后面已经有了一部分已经被移动到头部的连续的 1
                # 2、数字 0 后面没有被移动的 1
                nums[i], nums[ptr0] = nums[ptr0], nums[i]
                if ptr0 < ptr1:
                    # 对应情况1，在进行第一次交换后，数字0后的一个1被交换到了位置i，因此需要再次交换，将其放置于连续的1后面
                    nums[i], nums[ptr1] = nums[ptr1], nums[i]
                ptr0 += 1
                # 此处 ptr1 也需要 +1 的原因是：
                # 情况1下，第二次交换理应使ptr1 + 1；
                # 情况2下，数字0在首位，所以ptr1 必须得大于等于ptr0，因此同步+1
                ptr1 += 1