LeetCode OJ平台上Sort Colors題目算法探討

原題如下，意思就是說無序數組（由0,1,2組成），一遍掃描，把數組整理成若干個0-若干個1-若干個2這樣的序列。

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.

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

click to show follow up.

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.

想了一段時間，未果，於是前往Discuss區域圍觀。

帖子網址點擊打開鏈接

網友xianlei給出了一個精妙的方法，我理解之後，寫出代碼如下，因為有詳細的注釋，就不啰嗦了。

在草紙上模擬一下，或者單步調試一下，就會明白這個方法的精妙之處！！

public class Solution {
	static int[] A = {1,0};
    public static void sortColors(int[] A) {
    	int i = 0;//last index of array 0
    	int j = 0;//last index of array 1
    	int k = 0;//last index of array 2
    	for(int m = 0; m < A.length; m ++){
    		if(A[m] == 0){ // add 2 to the end of 2 array, replace the 1st 2 with 1, then insert 0 into 0 array, 
    			A[k++] = 2;
    			A[j++] = 1;
    			A[i++] = 0;
    		}
    		else if(A[m] == 1){// add 2 to the end of 2 array, then insert 1, at the location of the 1st 2
    			A[k++] = 2;
    			A[j++] = 1;
    		}
    		else{//add 2 to the end of 2 array
    			A[k++] = 2;
    		}
    	}        
    }
    public static void main(String args[]){
    	sortColors(A);
    }
}

網友lchen77提供了另一個很好的思路，我的實現代碼如下。

因為題目要求按照0,1,2的順序來排序，所以遇到0，與前面的A[k++]交換，遇到2與A[j--]交換。

需要注意的是，A[k]要麼等於0，要麼等於1，所以0與A[k++]交換之後，i不用--，整個前面的序列是合法的。

但是2與A[j--]交換之後，i要--，因為從數組尾部隨便一個數字與當前的2換完之後，必須還要驗證，以防不合法。

而且，循環的終止條件是i,j相遇，相遇的時候，還要執行一次，即循環終止條件是i>j

public class Solution {
	public static void sortColors(int[] A){
		int k = 0; //index for 0 array;
		int j = A.length-1;//index for 2 array
		for(int i = 0; i <= j;i ++){
			if(A[i] == 1){
				continue;
			}
			else if(A[i] == 0){
				A[i] = A[k];
				A[k++] = 0;
			}
			else{
				A[i] = A[j];
				A[j--] = 2;
				i --;
			}
		}
	}
}