75. Sort Colors

Leetcode 问题: 75. Sort Colors
Categories:
Tags:

题目

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.

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.

传入一整数阵列，不需回传任何资料，直接修改传入的整数阵列

传入的整数阵列数字限定只有 0, 1, 2，将传入的整数阵列依照大小排序（不可以用内建的排序函式库）

Example

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

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

答案

索引位置 0 1 2 3 4 5
数字 2 0 2 1 1 0
检查指标 V
分割指标 左指标 右指标

JavaScript

  1. 设定 左指标：0、右指标：整数阵列长度 -1，检查指标：0
    • 确保 左指标 左边数字都是 0
    • 确保 右指标 右边数字都是 2
  2. 当 检查指标 遇到 数字 0，将 检查指标数字 与 左指标数字 交换
    • 左指标 一定会变成 0，然后再移动 左指标 到下一个预计放 数字 0 的位置
  3. 当 检查指标 遇到 数字 2，将 检查指标数字 与 右指标数字 交换
    • 右指标 一定会变成 2，然后再移动 右指标 到下一个预计放 数字 2 的位置
    • 现在 检查指标的数字 是来自 右指标，所以可能是 0 或 1 ，需要再重新检查
    • 检查指标 每次都会往右移动，为了能够再检查一次，必须先将 检查指标减 1，让 检查指标 可以重新再检查一次
  4. 移动 检查指标 到下一个要检查的位置
/**
 * @param {number[]} numsList
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(numsList) {
    // 左指标
    let leftPointer = 0;
    // 右指标
    let rightPointer = numsList.length - 1;
    // 检查指标
    let checkPointer = 0;

    while (checkPointer <= rightPointer) {
        // 当检查指标还在右指标前面，表示还没检查完所有数字
        if (numsList[checkPointer] == 0) {
            // 当「检查指标」遇到 0，「检查指标」数字与「左指标」数字交换
            [numsList[leftPointer], numsList[checkPointer]] = [numsList[checkPointer], numsList[leftPointer]];
            // 左指标左边确认一定都是 0，往右移动
            leftPointer++;
        } else if (numsList[checkPointer] == 2) {
            // 当「检查指标」遇到 2，「检查指标」数字与「右指标」数字交换
            [numsList[rightPointer], numsList[checkPointer]] = [numsList[checkPointer], numsList[rightPointer]];
            // 右指标右边确认一定都是 2，往左移动
            rightPointer--;
            // 检查指标维持不变，因为交换到检查指标的数字可能是 1 或 0，所以需要重新检查一次
            checkPointer--;
        }

        // 移动到下一个检查指标
        checkPointer++;
    }

};

参考资料