75. Sort Colors

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */

题目给我们一个数字数组 nums，其中只包含三种数字：0、1、2， 分别代表红白蓝三种颜色

题目要求我们按照 012 的顺序把 nums 所有元素重新排列，让相同的颜色相邻

解题思路

这题看起来就是一个简单的手撕排序题，但是由于 nums 只包含三种数字，所以我们可以用三指针的方式将其优化到 O(n) 的复杂度

Javascript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    let left = 0
    let mid = 0
    let right = nums.length - 1
    while (mid <= right) {
        if (nums[mid] === 2) {
            ;[nums[right], nums[mid]] = [nums[mid], nums[right]]
            right--
            continue
        }
        if (nums[mid] === 0) {
            ;[nums[left], nums[mid]] = [nums[mid], nums[left]]
            left++
            mid++
            continue
        }
        mid++
    }
};