給定一個(gè)非負(fù)整數(shù)數(shù)組 A， A 中一半整數(shù)是奇數(shù)，一半整數(shù)是偶數(shù)。
對(duì)數(shù)組進(jìn)行排序，以便當(dāng) A[i] 為奇數(shù)時(shí)，i 也是奇數(shù)；當(dāng) A[i] 為偶數(shù)時(shí)， i 也是偶數(shù)。
你可以返回任何滿足上述條件的數(shù)組作為答案。

示例：

輸入：[4,2,5,7]
輸出：[4,5,2,7]
解釋：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也會(huì)被接受。

提示：

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000

思路：

兩個(gè)指針，分別指向奇數(shù)位和偶數(shù)位，已經(jīng)符合條件的項(xiàng)的末尾地址
遍歷數(shù)組：
假設(shè)遇到偶數(shù)位上的偶數(shù)，或奇數(shù)位上的奇數(shù)，則相應(yīng)指針后移
假設(shè)遇到偶數(shù)位上的奇數(shù)，或奇數(shù)位上的偶數(shù)，則交換當(dāng)前位和對(duì)應(yīng)指針位置元素。再從當(dāng)前位重新判斷

可能遇到的細(xì)節(jié)問題：當(dāng)指針后移的比遍歷要快的時(shí)候，要注意跳過一些已經(jīng)排好位置的項(xiàng)

性能分析：

時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

具體代碼：

class Solution {
    public void swap(int[] A, int a, int b){
        //交換用函數(shù)
        int t = A[a];
        A[a] = A[b];
        A[b] = t;
        return;
    }
    public int[] sortArrayByParityII(int[] A) {
        int sing = 1;
        int doub = 0;
        for(int i = 0; i < A.length; i++){
            if(A[i] % 2 == 1){ //第i項(xiàng)為奇數(shù)
                if(i % 2 == 1 && i >= sing){ // 索引也為奇數(shù),且不是前序處理過
                    sing += 2;
                    continue;
                }
                else if(i % 2 == 0){ //索引為偶數(shù)
                    swap(A, sing, i);
                    sing += 2;
                    i--;
                }
            }
            else{ //第i項(xiàng)為偶數(shù)
                if(i % 2 == 1){ //索引為奇數(shù)
                    swap(A, doub, i);
                    doub += 2;
                    i--;
                }
                else if(i % 2 == 0 && i >= doub){ //索引為偶數(shù),且不是前序處理過
                    doub += 2;
                    continue;
                }
            }
        }
        return A;
    }
}