21. Adjust the array order so that the odd number is ahead of the even number

Title Description 1

Input an integer array and implement a function to adjust the order of the numbers in the array so that all the odd numbers are in the
 In the first half, all even numbers are in the second half of the array

Analysis

Title Description 1 is the description given in the sword finger OFFER. Only an odd number is required before the array and an even number after it. It is not required to keep the relative position unchanged, which is relatively simple.

Code

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        // Method 1 double pointer
        if (array.empty()) return;
        int left = 0;
        int right = array.size() - 1;
        while (left < right) {
            while (left < right && array[left] % 2 != 0) {
                left++;
            }
            while (left < right && array[right] % 2 == 0) {
                right--;
            }
            if ((array[left] % 2 == 0) && (array[right] % 2 != 0)) {
                int tmp_val = array[left];
                array[left] = array[right];
                array[right] = tmp_val;
            }
        }
    }
};

Title Description 2

Input an integer array and implement a function to adjust the order of the numbers in the array so that all the odd numbers are in the
 In the first half, all even numbers are in the second half of the array, and the phase between odd and odd numbers, even and even numbers is ensured
 Same for position.

Analysis

The questions given on Niuke's website should be a little more complicated. We should not only ensure that the first half is odd, but also that the second half is even. And keep their relative positions unchanged. So the code given in topic description 1 can't be AC.
However, if we sacrifice a little space as a cost, there is also a very simple writing method, which gives the code space complexity O(n). Additional application space is required.

Weekend, more lazy, so, did not think of a better solution....

Code

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if (array.empty()) return;
        vector<int> odd;
        vector<int> even;
        for (int i = 0; i < array.size(); i++) {
            if (array[i] % 2 == 0) {
                even.push_back(array[i]);
            }
            else {
                odd.push_back(array[i]);
            }
        }
        int i = 0, j = 0;
        while (i < array.size() && j < odd.size()) {
            array[i] = odd[j];
            i++;
            j++;
        }
        j = 0;
        while (i < array.size() && j < even.size()) {
            array[i] = even[j];
            i++;
            j++;
        }
    }
};