Leetcode/F家微软 -- 75. Sort Colors(two pointer & counting sort)

75. Sort Colors （two pointer & counting sort）
 Medium
https://leetcode.com/problems/sort-colors/

Given an array with n objects colored red, white or blue, sort them so 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.

Pocket Gems Microsoft Facebook

解法1：3 pointer： 'i' point to the current position ,'left' point to the position right after 0, 'right' point to the position right before 2.

public class Solution {
    public void sortColors(int[] nums) {
        int i=0,left = 0,right=nums.length-1;
        while(i<=right){
            if(nums[i]==0){
                swap(nums,i,left);
                left++;
                i++;//left side is sorted already
            }else if(nums[i]==2){
                swap(nums,i,right);
                right--;
            }else{
                i++;//skip 1
            }
        }
    }
    public void swap(int[]nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

解法2： counting sort-- count frequency of 0,1,2 in nums. And fill back to nums.

public class Solution {
    public void sortColors(int[] nums) {
        int[] freq = new int[3];
        for(int i=0;i<nums.length;i++){
            freq[nums[i]]+=1;
        }
        int j = 0;//j is index in nums
        for(int i=0;i<freq.length;i++){
            int count  = freq[i];
            while (count>0){
                nums[j] = i;
                j++;
                count--;
            }
        }
    }
}