75. 颜色分类

题目描述 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 注意:不能使用代码库中的排序函数来解决这道题。 示例: 输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶: 一个直观的解决方案是使用计数排序的两趟扫描算法。首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗? https://leetcode-cn.com/problems/sort-colors/ 解法1 – 桶排序 – O(n) 就像题目描述的直观方法那样,我们声明一个长度为3的数组,下标为0,1,2的位置分别记录0、1、2数字出现的次数。第一次扫描填充桶,第二遍扫描从桶里取数,回填到数组中。 时间复杂度O(n),准确的说是O(2*n);空间复杂度O(1)。全部代码如下: 解法2 – Partition函数 – O(n) 记得快速排序的Partition函数吗?找一个pivot,两个指针指向数组两端,调用partition函数使得左边的元素都小于pivot;右边的元素都大于pivot。这里我们借用Partition函数的思想,用3个指针i、j、k。使得[0, i)的元素都是0、(j, |nums|)的元素都是2,而指针k扫描[0, |nums|)。 当k指向的当前元素是0,就把它与i所指的位置交换,然后i++;当k指向的当前元素是2,就把它与j所指的位置交换,然后j–;如果k指向的元素是1,那就k++。需要注意的是边界问题,k需要满足0<=i <=k <=j<|nums|。下面的条件k>=i实际上是限制i,如果我们不限制,就会使得i超越k,导致越界;对于变量j也是同理。 时间复杂度O(n),空间复杂度O(1)。全部代码如下:

Read more