75. Sort Colors

source: https://leetcode.com/problems/sort-colors/

Question

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.

排序

第一种思路比较直观，就是去排序，但是题目要求不能使用the library's sort function，所以要自己写一个简单的排序方法：

/**
 * 快排
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    const quickSort = arr => {
        if (arr.length < 2) return arr;
        const pivot = arr.pop();
        return [...quickSort(arr.filter(item => item < pivot)), pivot, ...quickSort(arr.filter(item => item >= pivot))];
    };
    const ret = quickSort([...nums]);
    nums.forEach((_, i) => (nums[i] = ret[i]));
};

单指针

还有一种思路，就是要把所有的0放到头部，所有的1放到第二部分。在这种情况下，可以遍历两次数组：

• 第一次遍历时，会把所有的0放到头部
• 第二次遍历时，保留上一次遍历的头部指针结束位置，把所有的1转移到第二部分

/**
 * 单指针
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    const swap = (i1, i2) => {
        const v = nums[i1];
        nums[i1] = nums[i2];
        nums[i2] = v;
    };
    let p = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            swap(i, p);
            p++;
        }
    }
    for (let i = p; i < nums.length; i++) {
        if (nums[i] === 1) {
            swap(i, p);
            p++;
        }
    }
}

双指针

因为单指针的方法需要遍历两次数组，所以很自然的想到可以用双指针的方式去做优化。

其中的指针指向可以理解下一个可以被交换的位置：p1可以理解为下一个交换1的指针位置，p2可以理解为下一个交换0的指针位置。

因为1必须在0的后面，而且p1和p2的位置都是各自独立的。所以在交换0的过程中，因为挤压了1的位置，所以p1也要+1. 同时，如果有p2 < p1, 说明把已经交换进来的1又交换出去了，这时候需要把他再交换回来。

/**
 * 双指针
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function (nums) {
    const swap = (i1, i2) => {
        if (i1 !== i2) {
            const v = nums[i1];
            nums[i1] = nums[i2];
            nums[i2] = v;
        }
    };
    let p1 = 0; // 1
    let p2 = 0; // 0
    nums.forEach((v, i) => {
        if (v === 1) {
            swap(i, p1);
            p1++;
        } else if (v === 0) {
            swap(i, p2);
            if (p2 < p1) swap(i, p1);
            p1++;
            p2++;
        }
    });
};

总结

这一题非常有层次，排序的话其实也可以写的很难。

单指针的方式很直观很容易写出来，但是要优化成双指针就需要很强的技巧，特别是0交换的场景，比较难考虑周全。

是一道很好的关于双指针的题目。