Heading

75.颜色分类 (opens new window)

Tags: algorithms facebook microsoft pocketgems array two-pointers sort

Langs: c cpp csharp dart golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (60.96%)
• Likes: 1765
• Dislikes: -
• Total Accepted: 618.9K
• Total Submissions: 1M
• Testcase Example: '[2,0,2,1,1,0]'

给定一个包含红色、白色和蓝色、共 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

 

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

/*
 * @lc app=leetcode.cn id=75 lang=javascript
 *
 * [75] 颜色分类
 * 插入排序
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  for (let i = 1; i < nums.length; i++) {
    const tmp = nums[i]
    let j = i
    while (j > 0 && tmp < nums[j - 1]) {
      nums[j] = nums[j - 1]
      j--
    }
    nums[j] = tmp
  }
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=75 lang=javascript
 *
 * [75] 颜色分类
 * 单指针
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  let i = 0
  const swap = (a, b) => {
    const tmp = nums[a]
    nums[a] = nums[b]
    nums[b] = tmp
  }

  const swapNumberToCurser = num => {
    while (nums[i] === num) {
      i++
    }
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] === num) {
        swap(i++, j)
        while (nums[i] === 0) {
          i++
        }
      }
    }
  }
  swapNumberToCurser(0)
  swapNumberToCurser(1)
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=75 lang=javascript
 *
 * [75] 颜色分类
 * 双指针
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  let p0 = 0
  let p1 = 0
  let i = 0
  const swap = (a, b) => {
    const tmp = nums[a]
    nums[a] = nums[b]
    nums[b] = tmp
  }
  while (i < nums.length) {
    if (nums[i] === 1) {
      swap(i, p1)
      p1++
    } else if (nums[i] === 0) {
      swap(i, p0)
      if (p0 < p1) {
        swap(i, p1)
      }
      p0++
      p1++
    }
    i++
  }
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=75 lang=javascript
 *
 * [75] 颜色分类
 * 双指针 优化
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
  let p0 = 0
  let p2 = nums.length - 1
  const swap = (a, b) => {
    const tmp = nums[a]
    nums[a] = nums[b]
    nums[b] = tmp
  }

  for (let i = 0; i <= p2; i++) {
    while (i <= p2 && nums[i] === 2) {
      swap(i, p2--)
    }
    if (nums[i] === 0) {
      swap(i, p0++)
    }
  }
}
// @lc code=end