颜色分类

题目

给定一个包含红色, 白色和蓝色, 一共 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 - 朴素解法

朴素做法是遍历数组, 将所有的元素放到哈希表中, key 是元素(即 0, 1, 2), val 是元素的个数. 然后再一趟循环, 按照 0, 1, 2 的顺序及其个数覆盖 nums 的每个元素.

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  const n = nums.length
  if (n < 2) return

  const map = {}

  for (let i = 0; i < n; i++) {
    const curr = nums[i]
    if (map[curr]) {
      map[curr] += 1
    } else {
      map[curr] = 1
    }
  }

  for (let i = 0; i < n; i++) {
    if (map[0] > 0) {
      nums[i] = 0
      map[0] -= 1
    } else if (map[1] > 0) {
      nums[i] = 1
      map[1] -= 1
    } else if (map[2] > 0) {
      nums[i] = 2
      map[2] -= 1
    }
  }

  return nums
}

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;
        }
    }
}