75 Sort Colour

總結:

1. 寫swap function 時要先輸入int [] nums 參數

  public void swap (int [] array, int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

無腦寫法:
計算所有顏色出現的次數, 再重寫array

class Solution {
    public void sortColors(int[] nums) {
        int count_red = 0;
        int count_white = 0;
        int count_blue = 0;
        for (int i=0; i<nums.length; i++){
            if (nums[i]==0){
                count_red++;
            }
            else if (nums[i]==1){
                count_white++;
            }
            else {
                count_blue++;
            }
        }
        int i=0;
        while(count_red!=0){
            nums[i++]=0;
            count_red--;
        }
        while(count_white!=0){
            nums[i++]=1;
            count_white--;
        }
        while(count_blue!=0){
            nums[i++]=2;
            count_blue--;
        }
    }
}

思路: 設左右指針於nums最左右的地方; 如循環指針i遇到0則swap(nums[i], nums[left]); left++
如遇到2則swap(nums[i], nums[right]); right++, 如遇到1則不變
1 pass寫法:

class Solution {
    public void sortColors(int[] nums) {
        //思路: 設左右指針於nums最左右的地方; 如循環指針i遇到0則swap(nums[i], nums[left]); left++
        //如遇到2則swap(nums[i], nums[right]); right++, 如遇到1則不變
        if (nums.length==0) return;
        int left =0;
        int right =nums.length-1;
        for (int i=left; i<=right; i++){
            if (nums[i]==0){
                swap(nums,i,left++);
            
            }
            else if (nums[i]==2){
                swap(nums,i--,right--);
                
            }
        }
    }
    public void swap (int [] array, int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}