75.颜色分类

颜色分类

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

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

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

解析

荷兰国旗问题，使用三指针一趟遍历完成排序。

/**
 * @param {number[]} nums
 * @return {void}
 */
var sortColors = function (nums) {
  let left = 0; // 0 的右边界
  let right = nums.length - 1; // 2 的左边界
  let curr = 0;

  while (curr <= right) {
    if (nums[curr] === 0) {
      [nums[curr], nums[left]] = [nums[left], nums[curr]];
      left++;
      curr++;
    } else if (nums[curr] === 2) {
      [nums[curr], nums[right]] = [nums[right], nums[curr]];
      right--;
      // curr 不加 1，因为交换过来的元素还没检查
    } else {
      curr++;
    }
  }
};

三指针法（荷兰国旗算法）：left 指向下一个 0 应放的位置，right 指向下一个 2 应放的位置，curr 遍历数组。时间复杂度 O(n)，一趟扫描。