75.颜色分类

链接：75.颜色分类
难度：Medium
标签：数组、双指针、排序
简介：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

题解 1 - typescript

• 编辑时间：2020-10-07
• 执行用时：92ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：利用自带排序算法，但不符合提议。

function sortColors(nums: number[]): void {
  nums.sort((a, b) => a - b);
}

题解 2 - typescript

• 编辑时间：2020-10-07
• 执行用时：100ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：双指针一遍循环，记录 p0 和 p2。

function sortColors(nums: number[]): void {
  const len = nums.length;
  let p0 = 0,
    p2 = len - 1;
  const swap = (i1: number, i2: number) =>
    i1 !== i2 && ([nums[i2], nums[i1]] = [nums[i1], nums[i2]]);
  for (let i = 0; i < len; i++) {
    while (i <= p2 && nums[i] === 2) {
      swap(i, p2);
      p2--;
    }
    if (nums[i] === 0) {
      swap(i, p0);
      p0++;
    }
  }
}

题解 3 - typescript

• 编辑时间：2021-05-07
• 执行用时：92ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：利用内部排序。

function sortColors(nums: number[]): void {
  nums.sort((a, b) => a - b);
}

题解 4 - typescript

• 编辑时间：2020-10-07
• 执行用时：96ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：双指针一遍循环，记录 p0 和 p1。

function sortColors(nums: number[]): void {
  let p0 = 0,
    p1 = 0;
  const len = nums.length;
  const swap = (i1: number, i2: number) =>
    i1 !== i2 && ([nums[i2], nums[i1]] = [nums[i1], nums[i2]]);
  for (let i = 0; i < len; i++) {
    if (nums[i] === 1) {
      swap(p1, i);
      p1++;
    } else if (nums[i] === 0) {
      swap(p0, i);
      p0 < p1 && swap(i, p1);
      p1++;
      p0++;
    }
  }
}

题解 5 - typescript

• 编辑时间：2020-10-07
• 执行用时：88ms
• 内存消耗：39.5MB
• 编程语言：typescript
• 解法介绍：遍历后交换 0 置前，2 置后。

function sortColors(nums: number[]): void {
  let c = 0;
  const len = nums.length;
  const swap = (i1: number, i2: number) =>
    i1 !== i2 && ([nums[i2], nums[i1]] = [nums[i1], nums[i2]]);
  // 0
  for (let i = 0; i < len; i++) {
    if (nums[i] === 0) {
      swap(c, i);
      cpp;
    }
  }
  // 2
  c = 0;
  for (let i = len - 1; i >= 0; i--) {
    if (nums[i] === 2) {
      swap(len - 1 - c, i);
      cpp;
    }
  }
}

题解 6 - typescript

• 编辑时间：2020-10-07
• 执行用时：84ms
• 内存消耗：39.6MB
• 编程语言：typescript
• 解法介绍：计数后重新生成数组。

function sortColors(nums: number[]): void {
  const cache: Record<number, number> = {
    0: 0,
    1: 0,
    2: 0,
  };
  for (const num of nums) {
    cache[num]++;
  }
  nums.length = 0;
  nums.push(
    ...new Array(cache[0]).fill(0),
    ...new Array(cache[1]).fill(1),
    ...new Array(cache[2]).fill(2)
  );
}