题目描述

给定一个非负整数数组 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

算法

(两次遍历) $O(n)$

1. 按照快速排序 split 的思路，将数组平均分为两部分，前半部分为偶数，后半部分为奇数。
2. 然后将前半部分奇数下标的数字和后半部分偶数下标的数字交换。

时间复杂度

• 两次遍历，时间复杂度为 $O(n)$。

空间复杂度

• 原地算法，空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int n = A.size();
        int l = 0, r = n - 1;

        while (l < r) {
            while (l < r && (A[l] & 1) == 0) l++;
            while (l < r && (A[r] & 1) == 1) r--;

            if (l < r) {
                swap(A[l], A[r]);
                l++;
                r--;
            }
        }

        for (int i = 1, j = n - 2; i < j; i += 2, j -= 2) {
            swap(A[i], A[j]);
        }

        return A;
    }
};