Sort Array By Parity II

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

 

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.
 

Note:

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

之前类似的题目，让我们将一个数组，分为一半奇数一半偶数，而这次则是需要偶数奇数间隔着来。这里直接暴力了，先分为偶数部分和奇数部分，然后再间隔地放入一个结果数组：

class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int fi = 0, li = A.size() - 1;
        while(fi < li) {
            if (A[fi] % 2 == 0) {
                fi++;
                continue;
            }
            while (li > fi) {
                if ( A[li] % 2 == 0) {
                    break;
                }
                li--;
            }
            if (li <= fi) {
                break;
            }
            std::swap(A[li], A[fi]);
            fi++; li--;
        }

        std::vector<int> res;
        res.reserve(A.size());
        for (int i = 0; i < A.size() / 2; i++) {
            res.push_back(A[i]);
            res.push_back(A[A.size() / 2 + i]);
        }
        return res;
    }
};