LeetCode Sort Array By Parity 陣列奇數偶數分類

本篇為LeetCode上演算法的簡單問題，Sort Array By Parity。

題目如下：

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

• 1 <= A.length <= 5000
• 0 <= A[i] <= 5000

輸入一組非負數的整數陣列，然後輸出偶數在前，奇數在後的陣列。偶數間及奇數間可任意排列。

一開始想到的就是在迴圈中從陣列中最前和最後的元素開始依序判斷是為奇數還是偶數，如果是的話就調換位置，但想了一陣子寫不出來，所以改用下面的方法，就是再宣告另一個長度同輸入陣列一樣的陣列，然後判斷輸入陣列中每個元素是偶數還是奇數，是偶數則從新陣列的最前面依序塞入，是奇數的話則從新陣列的最後面依序塞入。

public static int[] sortArrayByParity(int[] A) {

    int j = 0;
    int k = A.length - 1;
    int[] B = new int[A.length];
    for (int i = 0; i < A.length; i++) {
        if ((A[i] & 1) == 0) { // even
            B[j] = A[i];
            j++;
        } else { // odd
            B[k] = A[i];
            k--;
        }
    }

    return B;
}

缺點是空間複雜度是O(2N)，時間複雜度為O(N)。

下面則是我原本有想到但寫不出來的，這裡是參考討論區中別人寫的程式。

public static int[] sortArrayByParity(int[] A) {
    int s = 0; 
    int e = A.length - 1;
    while (s < e) {
        if ((A[s] & 1) == 1) { // 是否為奇數(even)
            if ((A[e] & 1) == 0) { // 是否為偶數(odd)
                int temp = A[s];
                A[s] = A[e];
                A[e] = temp;
                s++;
                e--;
            } else {
                e--;
            }
        } else {
            s++;
        }
    }
    return A;
}

做法順序如下：

1. 設定兩個索引，分別指向陣列最前及最後的數。
2. 迴圈陣列中的每個元素，從最前的數開始。
3. 若前面的數為奇數，則再判斷後面的數是否為偶數。若前面的數為偶數，則僅遞增前面的索引（因為前面的數若是偶數，留在前面即可。）。
4. 若前面的數為奇數，且若後面的數為偶數，則對調前後兩個數的位置，並遞增最前的索引，及遞減最後的索引。
5. 若前面的數為奇數，且若後面的數為奇數，則遞減最後的索引（因為後面的數若是奇數，就留在後面即可）。

如果想不懂的建議畫個陣列圖會比較清楚。

另外判斷一個整數為奇數或偶數除了用常見的if(n % 2 == 0)來判斷，也可以用if((n & 1) == 0)來判斷n為偶數還是奇數。

第二個解法是比較好的，時間複雜度平均優於O(N)，空間複雜度O(N)。

參考：

• Java 判斷一整數為偶數(even)或是奇數(odd)