905. Sort Array By Parity.md

905. Sort Array By Parity

思路

题目要求将一个数组中的偶数放在奇数前面。很简单用两个指针i和j就可以了，分别表示a[0, 1, ..., i-1]全部为偶数而a[j+1, j+2, ..., n-1]全部为奇数，所以i和j初始分别为0和n-1。然后就是循环，每个循环内部：

• 1. 如果A[i]为奇数那么交换A[i]和A[j]然后将j--，否则i++；
• 2. 如果A[j]为偶数那么交换A[i]和A[j]然后将i++，否则j--；

上面的1和2单独使用也是可以的。

另外STL中partition所干的就是此题要求的事，它会使所有使给定比较函数返回 true 的元素放在返回false的前面，所以我们只需要自定义比较函数就可以了。

C++

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        int i = 0, j = A.size() - 1;
        
        // 如果问题条件变一下, 例如将能被3整除的放在不能整除的前面, 我们只需要改这一行代码
        # define CONDITION(i) (A[i] & 1)
        
        while(i < j){
            if(i < j && CONDITION(i)) swap(A[i], A[j--]);
            else i++;
            
            if (i < j && !CONDITION(j)) swap(A[i++], A[j]);
            else j--;
        }
        return A;
    }
};

直接使用STL中的partition

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        partition(A.begin(), A.end(), [](int a) { return !(a & 1);});
        return A;
    }
};