颜色分类

题目

给定一个包含红色, 白色和蓝色, 一共 n 个元素的数组, 原地对它们进行排序, 使得相同颜色的元素相邻, 并按照红色, 白色, 蓝色顺序排列. 此题中, 我们使用整数 0, 1 和 2 分别表示红色, 白色和蓝色.

提示:

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

示例

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

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

题解

JavaScript

使用三指针, left 和 right 来标识 0 和 2 的位置, i 来标识 1 的位置.

var sortColors = function (nums) {
  const n = nums.length
  if (n < 2) return

  let left = 0 // 用来标识 0
  let i = 0 // 用来标识 1
  let right = n - 1 // 用来标识 2

  while (i <= right) {
    if (nums[i] === 0) {
      ;[nums[i], nums[left]] = [nums[left], nums[i]]
      left++
      i++
    } else if (nums[i] === 1) {
      i++
    } else {
      ;[nums[i], nums[right]] = [nums[right], nums[i]]
      right--
    }
  }
}

Rust

pub fn sort_colors(nums: &mut Vec<i32>) {
    let n = nums.n();
    if n < 2 {
        return;
    }

    let (mut left, mut right, mut i) = (0, n - 1, 0);

    while i <= right {
        if nums[i] == 0 {
            nums.swap(left, i);
            left += 1;
            i += 1;
        } else if nums[i] == 1 {
            i += 1;
        } else {
            nums.swap(i, right);
            if (right == 0) {
                break;
            }
            right -= 1;
        }
    }
}