[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]

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?

颜色分类。

给定一个包含红色、白色和蓝色，一共 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);
                cur++;
                left++;
            } 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 if (nums[cur] === 2) {
			swap(nums, cur, right);
			right--;
		}
	}
};

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