面接問題21.奇数が偶数より前になるように配列順序を調整

タイトル
1つの配列を入力し、すべての奇数が配列の前半に位置し、偶数が配列の後半に位置するように、配列内の数値の位置を調整する関数を実現します.例入力:nums=[1,2,3,4]出力:[1,3,2,4]注:[3,1,2,4]も答えです.ヒント:1<=nums.length <= 50000 1 <= nums[i] <= 10000
問題を解く構想.
3つの方法、暴力解法、首尾双針、速遅指針法.
第1の暴力解法は,記録のために新しい配列を導入することによって,配列全体を最初から遍歴し,奇数は新しい配列の始まりから格納し,偶数は最後のビットから格納し,この方法は時間と空間の複雑さがO(N)であり,アルゴリズム効率が最適ではない.
第2の首尾双指針法、アルゴリズム過程:

は、まず2つのポインタを定義し、それぞれ配列ヘッダと配列テールを指す.

ヘッドポインタは後方に循環し、奇数でない場合に遭遇するまで;偶数に遭遇するまで、テールポインタは前方に循環し、ヘッドポインタは常にテールポインタより小さい.

このときヘッドポインタは偶数、テールポインタは奇数、両者の交換位置、

を指す.

は、ヘッダポインタが出会うまで次のループを続けます.時間複雑度:O(N)、空間複雑度:O(10).

第3の速遅指針法は、その名の通り2つのポインタで実現され、2つのポインタはすべて最初から後ろ、速ポインタは奇数を後ろに探し、遅ポインタは偶数を後ろに探し、見つけたときに両者を交換し、速ポインタが配列の最後の位置になるまで.時間複雑度:O(N)、空間複雑度:O(10).
コード#コード#

class Solution {  
/************************      ***************************/
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1) return nums;
        int n = nums.length, a = 0,b = n-1;
        int[] newNums = new int[n];
        for(int i = 0;i<n;i++){
            if((nums[i]&1) == 1)
                newNums[a++] = nums[i];
            else
                newNums[b--] = nums[i];
        }
        return newNums;
    }

/************************       ***************************/
    public int[] exchange1(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1) return nums;
        int n = nums.length, i = 0,j = n-1;
        while(i < j){
            while((nums[i]&1) == 1 && i < j) i++; //       
            while((nums[j]&1) == 0 && i < j) j--; //       
            if(i < j) swap(nums,i,j);//  i    ，j    ，    
        }
        return nums;
    }
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
/*********************       ************************/
    public int[] exchange3(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1) return nums;
        int n = nums.length,fast = 0,low = 0;
        while(fast < n){
                if((nums[fast]&1 )== 1){
                    swap(nums,low,fast);
                    low++;
                }
                fast++;        
        }
        return nums;
    } 
}

変換は本題を変換することによって、索引が奇数の要素が配列の前半にあり、索引が偶数の要素が配列の後ろにあるようにする.アルゴリズムはやはり類似しており,二重ポインタによって実現される.

/********      (     )     ，     (     )      *********/
    public int[] exchange2(int[] nums) {
        if(nums == null || nums.length == 0 || nums.length == 1) return nums;
        int n = nums.length, i = 1,j = n-1;
        if((n&1) == 0) j--;
        while(i < j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i+=2;
            j-=2;
        }
        return nums;
    }