問題

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?

方法

三つの接近方がある。
１。O(nLogn): クイック・ソートーを使って並ぶ。
２。O(n): ゼロから二の数字が現れた回数を数える。
３。O(n): in-place swaping方法を実装する。

三番の方法を具現するのがこの問題のポイントだったらしい。

具現（Java）

１。O(nLogn): クイック・ソートーを使って並ぶ。

class Solution {
    
    private static void swap(int[] arr, int i, int j) {
        
        if (i != j) {
            
            arr[i] = arr[i] + arr[j];
            arr[j] = arr[i] - arr[j];
            arr[i] = arr[i] - arr[j];
        }
    }
    
    private static int partition(int[] arr, int l, int r) {
        
        int pivot = arr[(l + r) / 2];
        
        while (l <= r) {
            
            while (arr[l] < pivot) l++;
            while (pivot < arr[r]) r--;
            
            if (l <= r) swap(arr, l++, r--);
        }
        
        return l;
    }
    
    public static void qSort(int[] arr, int l, int r) {
        
        if (l >= r) return;
        
        int pivot = partition(arr, l, r);
        
        qSort(arr, l, pivot-1);
        qSort(arr, pivot, r);
    }
    
    public void sortColors(int[] nums) {
        
        qSort(nums, 0, nums.length-1);
    }
}

２。O(n): ゼロから二の数字が現れた回数を数える。

class Solution {
    
    public void sortColors(int[] nums) {
        
        int i = 0, j = 0;
        int[] cnt = new int[3];
    
        for(int num: nums) cnt[num]++;
        
        cnt[1] += cnt[0];
        cnt[2] += cnt[1];
        
        while (i < nums.length) {
            
            if (i >= cnt[j]) j++;
            else nums[i++] = j;
        }
    }
}

３。O(n): in-place swaping方法を実装する。

class Solution {
    
    public void sortColors(int[] nums) {
        
        int i = 0, j = 0, k = nums.length-1;
        
        while (j <= k) {
            
            if (nums[j] == 0) {
                
                nums[j++] = nums[i];
                nums[i++] = 0;
            }
            else if (nums[j] == 2) {
                
                nums[j] = nums[k];
                nums[k--] = 2;
            }
            else j++; // nums[j] == 1
        }
    }
}