[LeetCode] 75. Sort Colors

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.

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.

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

颜色分类，中文又叫做荷兰国旗。

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

好吧，题意是给一个数组，里面只有 0,1,2 三个数字，把数组排序成 [0, 0, 0, 1, 1, 1, ....1, 2, 2, 2, 2, 2] 的样子。

思路是 two pointer 夹逼扫描。这是一个有点类似快速排序里 partition 部分的做法。我们需要三个指针，cur，left 和 right。其中 left 和 right 分别指向数组最左边和最右边的位置，cur 指向的是当前需要处理的位置，表示当前这个位置要放什么元素。同时 cur 与 left 一样，也是从 0 开始。大体思路是我们尽量把 0 放到数组的左边，把 2 放到数组的右边，这样 1 也就尽可能被留在数组的中间部分了。最后附上官方的一个视频题解帮助理解。

开始遍历的时候，我们关注 cur 指针指向的元素

• 如果遇到 0，则放到左指针当前的位置（因为 0 都需要靠左嘛），left++，cur++。left++ 是因为 left 指针左边都是 0 了，所以要++，左边都处理完了；cur++ 是因为从 left 指针位置换过来的元素只有可能是 0 或 1，不可能是2，因为如果是2，他在之前就应该被移动到数组最右边了
• 如果遇到 1，不需要 swap 操作，只需要 cur++
• 如果遇到 2，则放到右指针的位置，同时 right--；因为 right 指针右边的部分处理完了，但是从 right 指针换过来的元素可能是 0 或者 1，所以 cur 不能++

时间O(n)

空间O(1)

Java实现

class Solution {
    public void sortColors(int[] nums) {
        // corner case
        if (nums == null || nums.length == 0) {
            return;
        }

        // normal case
        int left = 0;
        int right = nums.length - 1;
        int cur = 0;
        while (cur <= right) {
            if (nums[cur] == 0) {
                swap(nums, cur, left);
                left++;
                cur++;
            } else if (nums[cur] == 1) {
                cur++;
            } else {
                swap(nums, cur, right);
                right--;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    // corner case
    if (nums.length === 0 || nums === null) return;

    // normal case
    let left = 0;
    let right = nums.length - 1;
    let cur = 0;
    while (cur <= right) {
        if (nums[cur] === 0) {
            swap(nums, cur, left);
            cur++;
            left++;
        } else if (nums[cur] === 1) {
            cur++;
        } else {
            swap(nums, cur, right);
            right--;
        }
    }
};

var swap = function(nums, i, j) {
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
};

相关题目

75. Sort Colors

905. Sort Array By Parity

922. Sort Array By Parity II

LeetCode 题目总结