leetcode算法-颜色分类-75

本文主要是介绍leetcode算法-颜色分类-75，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode算法-颜色分类

题目来源:leetcode传送门

题目

给定一个包含红色、白色和蓝色，一共 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的个数,然后再重写给当前数组赋值就可以了。但是这个方法会扫描两次数组，进阶中要求在空间复杂度为O(n)的前提下使用一趟扫描完成。

要在一趟扫描完成这个动作，我们必须在遍历的过程中移动每个元素到正确的位置。那么什么才是正确的位置呢？显而易见，开头全为0,接着全是1,剩下的全为2,这样的位置。
由于只有三个元素,我们可以只移动其中两种元素到正确的位置，则移动结束后剩余的位置即为第三种元素的位置。

那么移动哪两个比较好呢？我选的是0和2,因为一个在开头一个在结尾，容易找到移动的目标位置。我们只需要设置两个变量next0和next2，next0代表下一个0应该移动到的位置，next2代表下一个2应该移动到的位置,然后遍历数组,如果当前元素值为0或2且当前索引与next不同，则交换当前索引元素与next索引元素，然后每次移动结束后,当前索引保持不变,以保证交换后的元素也能被正确地移动，然后移动next变量到下一个位置(next0++,next2- -)。

这样遍历一遍之后,所有的0和2都会被交换到正确的位置，而剩下的自然就是1，因为我们全程都是在原地进行交换，因此1也会到正确的位置。