這是悅樂書的第354次更新，第379篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級別的第216題（順位題號是922）。給定非負(fù)整數(shù)的數(shù)組A，A中的一半整數(shù)是奇數(shù)，而剩下的一半是偶數(shù)。

對數(shù)組進(jìn)行排序，以便每當(dāng)A[i]為奇數(shù)時，i就是奇數(shù); A[i]是偶數(shù)，i就是偶數(shù)。
你可以返回滿足此條件的任何答案數(shù)組。例如：

輸入：[4,2,5,7]
產(chǎn)出：[4,5,2,7]
說明：[4,7,2,5]，[2,5,4,7]，[2,7,4,5]也將被接受。

注意：

• 2 <= A.length <= 20000

• A.length％2 == 0

• 0 <= A [i] <= 1000
  
  

02 第一種解法

使用兩個List將奇數(shù)、偶數(shù)分別存起來，創(chuàng)建一個新的數(shù)組result，如果索引為奇數(shù)，就從存奇數(shù)的List中取值作為新數(shù)組的元素，反之就從存偶數(shù)的List中取值作為新數(shù)組的元素。

此解法的時間復(fù)雜度是O(N)，空間復(fù)雜度是O(N)。

public int[] sortArrayByParityII(int[] A) {
    List<Integer> odd = new ArrayList<Integer>();
    List<Integer> even = new ArrayList<Integer>();
    for (int num : A) {
        if (num%2 == 0) {
            even.add(num);
        } else {
            odd.add(num);
        }
    }
    int j = 0, k = 0;
    int[] result = new int[A.length];
    for (int i=0; i<result.length; i++) {
        if (i%2 == 0) {
            result[i] = even.get(j++);
        } else {
            result[i] = odd.get(k++);
        }
    }
    return result;
}

03 第二種解法

我們也可以直接從A中取值，同樣是新建一個result數(shù)組，對result數(shù)組新建兩個索引，一個從0開始，只做偶數(shù)索引，另一個從1開始，只做奇數(shù)索引，分兩次遍歷A數(shù)組，將對應(yīng)的元素和索引值存入result中。

此解法的時間復(fù)雜度是O(N)，空間復(fù)雜度是O(N)。

public int[] sortArrayByParityII2(int[] A) {
    int[] result = new int[A.length];
    int j = 0;
    for (int i=0; i<A.length; i++) {
        if (A[i]%2 == 0) {
            result[j] = A[i];
            j += 2;
        }
    }
    int k = 1;
    for (int i=0; i<A.length; i++) {
        if (A[i]%2 != 0) {
            result[k] = A[i];
            k += 2;
        }
    }
    return result;
}

04 第三種解法

針對上面的第二種解法，我們也可以只使用一次循環(huán)。

此解法的時間復(fù)雜度是O(N)，空間復(fù)雜度是O(N)。

public int[] sortArrayByParityII3(int[] A) {
    int[] result = new int[A.length];
    int j = 0, k = 1;
    for (int i=0; i<A.length; i++) {
        if (A[i]%2 == 0) {
            result[j] = A[i];
            j += 2;
        } else {
            result[k] = A[i];
            k += 2;
        }
    }
    return result;
}

05 第四種解法

雙指針。

定義兩個指針i和j，i代表偶數(shù)索引，從0開始；j代表奇數(shù)索引，從n-1開始（n為數(shù)組A的length），如果偶數(shù)索引位置對應(yīng)的元素為奇數(shù)，且奇數(shù)索引位置對應(yīng)的元素為偶數(shù)，就進(jìn)行元素交換。如果偶數(shù)索引位置對應(yīng)的元素為偶數(shù)，偶數(shù)索引i就加2，同理，奇數(shù)索引位置對應(yīng)的元素為奇數(shù)，奇數(shù)索引j就減2，循環(huán)結(jié)束條件為i不小于n或者j小于1。

此解法的時間復(fù)雜度是O(N)，空間復(fù)雜度是O(1)。

public int[] sortArrayByParityII4(int[] A) {
    int i = 0, j = A.length-1, n = A.length;
    while (i < n && j >= 1) {
        if (A[i]%2 == 1 && A[j]%2 == 0) {
            int tem = A[j];
            A[j] = A[i];
            A[i] = tem;
        }
        if (A[i]%2 == 0) {
            i += 2;
        }
        if (A[j]%2 == 1) {
            j -= 2;
        }
    }
    return A;
}

06 小結(jié)

算法專題目前已連續(xù)日更超過六個月，算法題文章222+篇，公眾號對話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部內(nèi)容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對我最大的回報(bào)和支持！