LeetCode: 905. Sort Array By Parity

题目描述

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

1 <= A.length <= 5000
0 <= A[i] <= 5000

解题思路

一个游标从左到右查找奇数，一个游标从右向左查找偶数，然后交换这两个数的位置。重复上述过程直到两游标相遇。

AC 代码

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        vector<int> ans(A.begin(), A.end());

        int i = 0, j = ans.size()-1;

        while(i < j)
        {
            while(i < j && ans[j]%2 == 1) --j;
            while(i < j && ans[i]%2 == 0) ++i;
            if(i < j) swap(ans[i++], ans[j--]);
        }

        return ans;
    }
};