# 0075. 颜色分类 ## 题目地址(75. 颜色分类) <https://leetcode-cn.com/problems/sort-colors/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个包含红色、白色和蓝色，一共 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)O(n)O(n)，需要遍历数组两次。 ## 解法二 我们可以把数组分成三部分，前部（全部是 0），中部（全部是 1）和后部（全部是 2）三个部分。每一个元素（红白蓝分别对应 0、1、2）必属于其中之一。将前部和后部各排在数组的前边和后边，中部自然就排好了。 我们用三个指针，设置两个指针 begin 指向前部的末尾的下一个元素（刚开始默认前部无 0，所以指向第一个位置），end 指向后部开头的前一个位置（刚开始默认后部无 2，所以指向最后一个位置），然后设置一个遍历指针 current，从头开始进行遍历。 这种思路的时间复杂度也是O(n)O(n)O(n), 只需要遍历数组一次。 ### 关键点解析 - 荷兰国旗问题 - counting sort ### 代码 代码支持： Python3 Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">sortColors</span><span class="hljs-params">(self, nums: List[int])</span> -> <span class="hljs-keyword">None</span>:</span> <span class="hljs-string">""" Do not return anything, modify nums in-place instead. """</span> p0 = cur = <span class="hljs-params">0</span> p2 = len(nums) - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> cur <= p2: <span class="hljs-keyword">if</span> nums[cur] == <span class="hljs-params">0</span>: nums[cur], nums[p0] = nums[p0], nums[cur] p0 += <span class="hljs-params">1</span> cur += <span class="hljs-params">1</span> <span class="hljs-keyword">elif</span> nums[cur] == <span class="hljs-params">2</span>: nums[cur], nums[p2] = nums[p2], nums[cur] p2 -= <span class="hljs-params">1</span> <span class="hljs-keyword">else</span>: cur += <span class="hljs-params">1</span> ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(1)O(1)O(1) 大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。