Sort Array By Parity II Solutions in C++

// Source : https://leetcode.com/problems/sort-array-by-parity-ii/
// Author : Hao Chen
// Date   : 2019-03-26



class Solution {
public:
    bool isEven(int &x) {
        return x % 2 == 0;
    }
    vector<int> sortArrayByParityII(vector<int>& A) {
        //two pointer, `even` and `odd`,
        //  - `even` pointer step into even position
        //  - `odd` pointer step into odd position.
        // if `even` points to odd number, and `odd` points to even number switch them.
        int even = 0;
        int odd = 1;
        while(even < A.size() && odd < A.size() ) {
            if ( !isEven(A[even]) && isEven(A[odd]) ) swap( A[even], A[odd] );
            if ( isEven(A[even]) ) even += 2;
            if ( !isEven(A[odd]) ) odd += 2;
        }
        return A;
    }
};

/// Source : https://leetcode.com/problems/sort-array-by-parity-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-10-13

#include <iostream>
#include <vector>

using namespace std;


/// Seperate odd and even elements into different vectors
/// Time Complexity: O(n)
/// Space Complexity: O(2*n)
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {

        vector<int> even, odd;
        for(int i = 0; i < A.size(); i ++)
            if(A[i] % 2)
                odd.push_back(A[i]);
            else
                even.push_back(A[i]);

        vector<int> ret;
        int p_odd = 0, p_even = 0;
        for(int i = 0; i < A.size(); i ++)
            if(i % 2)
                ret.push_back(odd[p_odd ++]);
            else
                ret.push_back(even[p_even ++]);
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/sort-array-by-parity-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-10-13

#include <iostream>
#include <vector>

using namespace std;


/// Two pass to deal with odd and even elements seperately
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {

        vector<int> ret(A.size());
        int p_even = 0;
        for(int a: A)
            if(a % 2 == 0){
                ret[p_even] = a;
                p_even += 2;
            }

        int p_odd = 1;
        for(int a: A)
            if(a % 2){
                ret[p_odd] = a;
                p_odd += 2;
            }
        return ret;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/sort-array-by-parity-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-10-14

#include <iostream>
#include <vector>

using namespace std;


/// Make the change in place
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {

        for(int i = 0; i < A.size(); i ++)
            if(i % 2 == 0 && A[i] % 2){
                int j = i + 1;
                for(; j < A.size(); j += 2)
                    if(A[j] % 2 == 0)
                        break;
                swap(A[i], A[j]);
            }
            else if(i % 2 && A[i] % 2 == 0){
                int j = i + 1;
                for(; j < A.size(); j += 2)
                    if(A[j] % 2)
                        break;
                swap(A[i], A[j]);
            }
        return A;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/sort-array-by-parity-ii/description/
/// Author : liuyubobobo
/// Time   : 2018-10-14

#include <iostream>
#include <vector>

using namespace std;


/// Make the change in place
/// and the code clearer :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {

        int j = 1;
        for(int i = 0; i < A.size(); i += 2)
            if(A[i] % 2){
                for(; j < A.size(); j += 2)
                    if(A[j] % 2 == 0)
                        break;
                swap(A[i], A[j]);
            }
        return A;
    }
};


int main() {

    return 0;
}