Sort Colors

Medium

Given an array with_n_objects colored red, white or blue, sort themin-placeso that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.

  First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

• Could you come up with a one-pass algorithm using only constant space?

Solution

https://www.jiuzhang.com/solution/sort-colors/#tag-other

使用一次扫描的办法。 设立三根指针，left, index, right。定义如下规则：

left 的左侧都是 0（不含 left） right 的右侧都是 2（不含 right） index 从左到右扫描每个数，如果碰到 0 就丢给 left，碰到 2 就丢给 right。碰到 1 就跳过不管。

public class Solution {
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */
    public void sortColors(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        int pl = 0, pr = nums.length - 1;
        int index = 0;
        while (index <= pr) {
            if (nums[index] == 0) {
                swap(nums, pl, index);
                index++;
                pl++;
            }
            else if (nums[index] == 2) {
                swap(nums, pr, index);
                pr--;
            }
            else {
                index++;
            }
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

Counting Sort (Buckets) - (0 ms, faster than 100.00%)

class Solution {
    private static final int MAX = 3;

    public void sortColors(int[] nums) {
        int[] buckets = new int[MAX];

        for(int num : nums) {
            buckets[num]++;
        }

        int i = 0;
        for(int val = 0; val < MAX; val++) {
            for(int count = 0; count < buckets[val]; count++) {
                nums[i++] = val;
            }
        }
    }
}

Reference

https://leetcode.com/problems/sort-colors/discuss/26500/Four-different-solutions