# 0075. 颜色分类
### 题目地址(75. 颜色分类)
### 题目描述
```
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
```
### 前置知识
* [荷兰国旗问题](https://en.wikipedia.org/wiki/Dutch_national_flag_problem)
* 排序
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
这个问题是典型的荷兰国旗问题 （[https://en.wikipedia.org/wiki/Dutch\_national\_flag\_problem）。](https://en.wikipedia.org/wiki/Dutch_national_flag_problem%EF%BC%89%E3%80%82) 因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。
### 解法一 - 计数排序
* 遍历数组，统计红白蓝三色球（0，1，2）的个数
* 根据红白蓝三色球（0，1，2）的个数重排数组
这种思路的时间复杂度：$O(n)$，需要遍历数组两次（Two pass）。
### 解法二 - 挡板法
我们可以把数组分成三部分，前部（全部是 0），中部（全部是 1）和后部（全部是 2）三 个部分。每一个元素（红白蓝分别对应 0、1、2）必属于其中之一。
核心目标就是确定三个部分的分割点，不难知道分割点有两个。
并且我们如果将前部和后部各排在数组的前边和后边，中部自然就排好了。
具体来说，可以用三个指针。
* begin 指向前部的末尾的下一个元素（刚开始默认前部无 0，所以指向第一个位置）
* end 指向后部开头的前一个位置（刚开始默认后部无 2，所以指向最后一个位置）
* 遍历指针 current，从头开始进行遍历。
形象地来说地话就是有两个挡板，这两个挡板具体在哪事先我们不知道，我们的目标就是移 动挡板到合适位置，并且使得挡板间的每一部分都是同一个的颜色。
还是以题目给的样例来说，初始化挡板位置为最左侧和最右侧：
读取第一个元素是 2，它应该在右边，那么我们移动右边地挡板，使得 2 跑到挡板的右边 。
> 带有背景色的圆圈 1 是第一步的意思。
并将其和移动挡板后挡板右侧地元素进行一次交换，这意味着“被移动挡板右侧元素已就位 ”。
。。。
整个过程大概是这样的：
这种思路的时间复杂度也是$O(n)$, 只需要遍历数组一次。空间复杂度为 $O(1)，因为我们 没有使用额外的空间。
#### 关键点解析
* 荷兰国旗问题
* counting sort
#### 代码
代码支持： Python3, CPP
Python3 Code:
```py
class Solution:
def sortColors(self, strs):
# p0 是右边界
# p1 是右边界
# p2 是左边界
# p1 超过 p2 结束
p0, p1, p2 = 0, 0, len(strs) - 1
while p1 <= p2:
if strs[p1] == 'blue':
strs[p2], strs[p1] = strs[p1], strs[p2]
p2 -= 1
elif strs[p1] == 'red':
strs[p0], strs[p1] = strs[p1], strs[p0]
p0 += 1
p1 += 1 # p0 一定不是 blue，因此 p1 += 1
else: # p1 === 'green'
p1 += 1
return strs
```
CPP Code:
```cpp
class Solution {
public:
void sortColors(vector& nums) {
int r = 0, g = 0, b = 0;
for (int n : nums) {
if (n == 0) {
nums[b++] = 2;
nums[g++] = 1;
nums[r++] = 0;
} else if (n == 1) {
nums[b++] = 2;
nums[g++] = 1;
} else nums[b++] = 2;
}
}
};
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
### 相关题目
* [面试题 02.04. 分割链表](https://leetcode-cn.com/problems/partition-list-lcci/)
参考代码：
```py
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
l1 = cur = head
while cur:
if cur.val < x:
cur.val, l1.val = l1.val, cur.val
l1 = l1.next
cur = cur.next
return head
```
**复杂度分析**
* 时间复杂度：$O(N)$，其中 N 为链表长度。
* 空间复杂度：$O(1)$。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我 的 LeetCode 题解仓库： 。 目前已经 37K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/75.sort-colors.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.