颜色分类

颜色分类问题如何用三路划分求解？

• 问题: 数组只含 0、1、2, 原地排序使相同值相邻;
• 以 1 为基准做三路划分: left 左侧放 0, right 右侧放 2;
• 用 i 从左向右扫描:
  • nums[i] 为 0: 与 left 交换, left 与 i 一同右移;
  • nums[i] 为 1: 跳过;
  • nums[i] 为 2: 与 right 交换, right 左移, i 原地重判;

function sortColors(nums: number[]): void {
  let left = 0;
  let right = nums.length - 1;
  for (let i = 0; i <= right; i++) {
    if (nums[i] === 0) {
      [nums[i], nums[left]] = [nums[left], nums[i]];
      left++;
    } else if (nums[i] === 1) {
      continue;
    } else {
      [nums[i], nums[right]] = [nums[right], nums[i]];
      right--;
      i--;
    }
  }
}

为什么交换 2 之后必须回退 i？

• right 位置换过来的元素尚未判定, 必须重新检查该位置;
• 交换 0 后不需要回退: 换到 left 位置的一定是 0 或 1 中已判定的元素;

三路划分与快速排序是什么关系？

• 三路划分是快速排序面对大量重复键时的优化;
• 做法: 把数组分成"小于、等于、大于"基准的三段, 等于段无需再递归;
• 复杂度: 时间 O(n), 空间 O(1);