leetcode.75.颜色分类

题目描述

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

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

注意:

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

示例:

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

进阶：

1 2	一个直观的解决方案是使用计数排序的两趟扫描算法。首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

标签排序 双指针 数组

解题思路

这道题的排序不是排[2,0,2,1,1,0]，这个只是抽象出来的。。

所以不止 sort 不能用，冒泡插入之类的排序也是不行的。

解法一：三指针

时间复杂度O(n)

我们可以把数组分成三部分，前部（全部是0），中部（全部是1）和后部（全部是2）三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。

将前部和后部各排在数组的前边和后边，中部自然就排好了。

我们用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。

本解法的思路是沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。

初始化0的最右边界：p0 = 0。在整个算法执行过程中 nums[idx < p0] = 0.
初始化2的最左边界：p2 = n - 1。在整个算法执行过程中 nums[idx > p2] = 2.
初始化当前考虑的元素序号：curr = 0.
While curr <= p2 :
1. 若 nums[curr] = 0 ：交换第 curr个和第p0个元素，并将指针都向右移。
2. 若 nums[curr] = 2 ：交换第 curr个和第 p2个元素，并将 p2指针左移。
3. 若 nums[curr] = 1 ：将指针curr右移。

var sortColors = function(nums) {
  if (nums.length > 1) {
    var p0 = 0,
      p2 = nums.length - 1,
      curr = 0
  }
  while (curr <= p2) {
    if (nums[curr] == 0) {
      ;[nums[p0], nums[curr]] = [nums[curr], nums[p0]]
      p0++
      curr++
    } else if (nums[curr] == 2) {
      ;[nums[p2], nums[curr]] = [nums[curr], nums[p2]]
      p2--
    } else {
      curr++
    }
  }
}

解法二：计数排序

时间复杂度O(n)

这样写也能过，但是这个不算是原地排序了。。

我们看一下计数排序是怎么运作

假设我们有[1,2,3,1,0,4]这六个数，这里面最大的值为4

那么我们创建一个长度为4+1的数组，每个元素默认为0。

这相当于选举排序，一共有6个投票箱，1就投1号箱，0就投入0号箱。

注意，这些箱本来就是已经排好序，并且箱的编号就是代表原数组的元素。当全部投完时，0号箱有1个，1号箱有2个，2号箱有1个，3号箱有1，4号箱有1个。

然后我们从这些箱的所有数依次出来，放到新数组，就神奇地排好序了。

计数排序没有对元素进行比较，只是利用了箱与元素的一一对应关系，根据箱已经排好序的先决条件，解决排序。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let stackLength = Math.max(...nums)   // 获取数组里最大值 
    let countArr = Array(stackLength + 1).fill(0)   // 创建长度为最大值+1的临时数组，并将元素设为0
    
    for(let i = 0; i < nums.length; i ++){
        // 遍历数组，在临时数组对应 key 上计数
        countArr[nums[i]] += 1
    }
    
    nums.length = 0   // 因为题目要求原地排序
    
    for(let i = 0; i < countArr.length; i++) {
        // 把计数数组按顺序放回原数组
        while(countArr[i]) {
            nums.push(i)
            countArr[i]--
        }
    }
};