LC 75. 颜色分类

题目描述

这是 LeetCode 上的 75. 颜色分类 ，难度为 中等。

给定一个包含红色、白色和蓝色、共 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

进阶：

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

---

双指针

该题为经典的荷兰国旗问题，由于题目本质是要我们将数分成三段。

因此除了使用一个变量 idx 代指处理到哪一个 $nums[i]$ 以外，至少还需要两个变量来代指三段的边界：

• 变量 l 为下一个填入 0 的位置（因此范围 $[0, l - 1]$ 均为 0，初始化 $l = 0$，代表空集）
• 变量 r 为下一个填入 2 的位置（因此范围 $[r + 1, n - 1]$ 均为 2，初始化 $r = n - 1$，代表空集)

由于 $[0, idx - 1]$ 均为处理过的数值（即 0 和 2 必然都被分到了两端），同时 $l - 1$ 又是 0 的右边界，因此 $[l, idx - 1]$ 为 1 的区间，而 $[idx, r]$ 为未处理的数值。

上述几个变量的定义是该题唯一需要理清的地方。

不失一般性，根据当前处理到的 $nums[idx]$ 进行分情况讨论：

• $nums[idx] = 0$：此时将其与位置 l 进行互换（记住 l 为下一个待填入 0 的位置，同时 $[l, idx - 1]$ 为 1 的区间），本质是将 $nums[idx]$ 的 0 和 $nums[l]$ 的 1 进行互换，因此互换后将 l 和 idx 进行右移；
• $nums[idx] = 1$：由于 $[l, idx - 1]$ 本身就是 1 的区间，直接将 idx 进行右移即可；
• $nums[idx] = 2$：此时将其与位置 r 进行互换（r 为下一个待填入 2 的位置，但 $[idx, r]$ 为未处理区间），也就是我们互换后，只能明确换到位置 $nums[r]$ 的位置为 2，可以对 r 进行左移，但不确定新 $nums[idx]$ 为何值，因此保持 idx 不变再入循环判断。

最后当 $idx > r$（含义为未处理区间为空集），整个分三段过程结束。

Java 代码：

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1, idx = 0;
        while (idx <= r) {
            if (nums[idx] == 0) swap(nums, l++, idx++);
            else if (nums[idx] == 1) idx++;
            else swap(nums, idx, r--);
        }
    }
    void swap(int[] nums, int i, int j) {
        int c = nums[i];
        nums[i] = nums[j];
        nums[j] = c;
    }
}

TypeScript 代码：

function sortColors(nums: number[]): void {
    const n = nums.length
    let l = 0, r = n - 1, idx = 0
    while (idx <= r) {
        if (nums[idx] == 0) swap(nums, l++, idx++)
        else if (nums[idx] == 1) idx++
        else swap(nums, idx, r--)
    }
}
function swap(nums: number[], i: number, j: number): void {
    const c = nums[i]
    nums[i] = nums[j]
    nums[j] = c
}

Python 代码：

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        n = len(nums)
        l, r, idx = 0, n - 1, 0
        while idx <= r:
            if nums[idx] == 0:
                nums[l], nums[idx] = nums[idx], nums[l]
                l += 1
                idx += 1
            elif nums[idx] == 1:
                idx += 1
            else:
                nums[r], nums[idx] = nums[idx], nums[r]
                r -= 1

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.75 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。