75. 颜色分类

---

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/sort-colors

题目

---

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

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

注意: 不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]

进阶：

一个直观的解决方案是使用计数排序的两趟扫描算法。

首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

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

解题思路

---

思路：计数排序、双指针

先看题目，这道题给定的数组中只包含了三种颜色：红色、白色和蓝色，分别用整数 0，1 和 2 表示。

题目的要求是 原地 对数组中的元素进行排序，使得相同颜色的元素相邻，按照红、白、蓝的顺序排序。

计数排序

先看进阶部分的第一段内容。这里明确给定计数排序算法的思路，那么我们先按照这个思路，先尝试解决问题。

题目仅有 0、1 和 2 三个元素，先创建长度为 3 的数组 count_array，用以迭代统计三个元素的个数；遍历，根据 count_array 记录的个数，按照 0、1、2 的顺序重写数组。

具体实现代码如下。（这里代码并不严谨，仅供参考）

from typing import List class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # 因为只有 0，1，2 三个元素 # 这里的 3 指的数组长度 # 数组末尾索引对应的是最大元素 2 count_arry = [0] * 3 # 遍历统计元素出现的个数 for i in range(len(nums)): count_arry[nums[i]] += 1 index = 0 # 重写数组，3 表示 count_array 数组长度 for i in range(3): for _ in range(count_arry[i]): nums[index] = i index += 1

双指针

这里主要说明下双指针的思路。因为数组给定的元素中只包含 0、1、2 （红、白、蓝）三个元素，而题目的要求是对数组进行排序，使得颜色相同的元素相邻，按照红、白、蓝的顺序排序。

直接看结论，因为只有 3 个元素。我们发现，数组中的 0 最终都排列在前面，而 2 最终排列在后面。也就是说，在遍历的数组时，如果遇到 0，我们将其放到前面；遇到 2，将其放到后面；而最终剩下的 1，则会在 0 与 2 之间。具体的做法如下：

初始化双指针 p1、p2。其中 p1 指向数组头部，p2 指向数组尾部。定义游标 cur 指向数组头部，从左向右遍历数组： 当 nums[cur] == 0 时，交换 cur 对应的元素与 p1 对应的元素，同时将 cur、p1 往后移动一个位置。这里可能存在这样的情况，nums[cur] 等于 0，但 cur 与 p1 重合，这里直接将 cur、p1 往后移动一个位置；当 nums[cur] == 2 时，交换 cur 对应的元素与 p2 对应的元素，仅将 p2 往前移动一个位置。若不是上面两种情况（也就是 cur 指向 1 时），仅将 cur 往后移动一个位置。 由于遍历从左往右，p2 由右往前移动。所以当 cur 大于 p2 时，停止遍历。

下面给出图示（以题目示例为例）：

具体代码实现如下。

class Solution: def sortColors(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ n = len(nums) # 初始化双指针， # p1 指向数组头部 # p2 指向数组尾部 p1 = 0 p2 = n-1 # 定义游标 cur cur = 0 # 从左往右遍历 while cur <= p2: # 当 cur 指向元素等于 0 时， # 与 p1 对应的元素进行替换 # 移动 cur、p1 if nums[cur] == 0: # 如果重合直接移动 cur、p1 if cur != p1: nums[p1], nums[cur] = nums[cur], nums[p1] cur += 1 p1 += 1 # 当 cur 指向元素等于 2 时， # 与 p2 对应的元素进行替换 # 往前移动 p2 elif nums[cur] == 2: nums[p2], nums[cur] = nums[cur], nums[p2] p2 -= 1 # 不属于上面的情况时，移动游标 cur else: cur += 1

复杂度分析

时间复杂度：$O(n)$，$n$ 是数组 $nums$ 的长度。空间复杂度：$O(1)$，仅使用了常数个变量。

欢迎关注

---

公众号 【书所集录】

---

若有错误，烦请指出，欢迎指点交流。