LeetCode.922-按奇偶排序數組 II(Sort Array By Parity II)

這是悅樂書的第354次更新，第379篇原創

01 看題和準備

今天介紹的是

LeetCode

算法題中

Easy

級别的第

216

題（順位題号是

922

）。給定非負整數的數組A，A中的一半整數是奇數，而剩下的一半是偶數。

對數組進行排序，以便每當A[i]為奇數時，i就是奇數; A[i]是偶數，i就是偶數。

你可以傳回滿足此條件的任何答案數組。例如：

輸入：[4,2,5,7]

産出：[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

将奇數、偶數分别存起來，建立一個新的數組

result

，如果索引為奇數，就從存奇數的

List

中取值作為新數組的元素，反之就從存偶數的

List

中取值作為新數組的元素。

此解法的時間複雜度是

O(N)

，空間複雜度是

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

數組，對

result

數組建立兩個索引，一個從0開始，隻做偶數索引，另一個從1開始，隻做奇數索引，分兩次周遊A數組，将對應的元素和索引值存入

result

中。

O(N)

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 第三種解法

針對上面的第二種解法，我們也可以隻使用一次循環。

O(N)

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代表偶數索引，從0開始；j代表奇數索引，從n-1開始（n為數組A的length），如果偶數索引位置對應的元素為奇數，且奇數索引位置對應的元素為偶數，就進行元素交換。如果偶數索引位置對應的元素為偶數，偶數索引i就加2，同理，奇數索引位置對應的元素為奇數，奇數索引j就減2，循環結束條件為i不小于n或者j小于1。

O(N)

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 小結

算法專題目前已連續日更超過六個月，算法題文章222+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！