Sort Colors

Description

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Follow up:

• Could you solve this problem without using the library's sort function?
• Could you come up with a one-pass algorithm using only O(1) constant space?

 

Example 1:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2:

Input: nums = [2,0,1]
Output: [0,1,2]

Example 3:

Input: nums = [0]
Output: [0]

Example 4:

Input: nums = [1]
Output: [1]

 

Constraints:

• n == nums.length
• 1 <= n <= 300
• nums[i] is 0, 1, or 2.

Solution(javascript)

/** Counting Sort
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
// const sortColors = function (nums) {
//   let zeros = 0
//   let ones = 0
//   for (const n of nums) {
//     if (n === 0) {
//       zeros += 1
//     } else if (n === 1) {
//       ones += 1
//     }
//   }

//   let i = 1
//   while (i <= nums.length) {
//     if (i <= zeros) {
//       nums[i - 1] = 0
//     } else if (i <= zeros + ones) {
//       nums[i - 1] = 1
//     } else {
//       nums[i - 1] = 2
//     }
//     i += 1
//   }
// }

// https://en.wikipedia.org/wiki/Dutch_national_flag_problem
//  分三份，确定每一份的下标位置, 有点类似快排的思路
const sortColors = function (nums) {
  const swap = (i, j) => {
    const temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
  }
  let zero = 0
  let one = 0
  let two = nums.length - 1

  while (one <= two) {
    if (nums[one] < 1) {
      swap(zero, one)
      zero += 1
      one += 1
    } else if (nums[one] === 1) {
      one += 1
    } else {
      swap(one, two)
      two -= 1
    }
  }
}