Lt75. 颜色分类

75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n *个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
*注意:**
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：

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

思路

计数两次遍历

使用一个数组记录颜色出现个数，再重新修改

双指针

使用左右双指针，将 0 放到前面，将 2 放到后面即可

解答

计数两次遍历

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  const colorCount = [0, 0, 0];
  for (let i = 0; i <= nums.length - 1; i++) {
    colorCount[nums[i]]++;
  }
  let count = 0;
  for (let i = 0; i <= nums.length - 1; i++) {
    while (colorCount[count] === 0) {
      count++;
    }
    nums[i] = count;
    colorCount[count]--;
  }
};

双指针

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  let left = 0,
    right = nums.length - 1;
  for (let i = 0; i <= right; i++) {
    if (nums[i] === 0) {
      [nums[left], nums[i]] = [nums[i], nums[left]];
      left++;
    } else if (nums[i] === 2) {
      [nums[right], nums[i]] = [nums[i], nums[right]];
      right--;
      //i--的原因是，可能将2交换回来，需要重新判断
      i--;
    }
  }
};