75. Sort Colors (opens new window)

Description

Difficulty: Medium

Related Topics: Array (opens new window), Two Pointers (opens new window), Sorting (opens new window)

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

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

You must solve this problem without using the library's sort function.

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]

Constraints:

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

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 * 思路：借助快速排序 partition 过程的一趟扫描法
 * 回顾快速排序 partition 过程：随机选择一个元素作为切分元素（pivot），然后经过一次扫描，通过交换不同位置的元素使得数组按照数值大小分成以下3个部分：<pivot ==pivot >pivot
 */
var sortColors = function(nums) {
    let [i, l, r] = [0, 0, nums.length - 1];
    
    while (i <= r) {
        if (!nums[i]) [nums[i++], nums[l++]] = [nums[l], nums[i]];
        else if (nums[i] === 2) [nums[i], nums[r--]] = [nums[r], nums[i]];        
        else i++;                                    
    }                        
};