這是悅樂書的第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ā)就是對我最大的回報和支持！