题目的主要信息：

• 输入一个长度为nnn的数组，经过调整使所有的奇数在前半部分，所有的偶数在后半部分
• 奇数与奇数之间、偶数与偶数之间的相对位置关系不固定
• 要求：时间复杂度$O(n)O(n)$，空间复杂度$O(n)O(n)$

方法一：复制法

具体做法：

可以准备一个待返回的长度为$nn$的数组，我们先遍历数组array找到其中的奇数有多少个，然后准备两个起始坐标，x表示奇数的起始坐标从0开始，y表示偶数的起始坐标，从刚刚找到的奇数个数开始，然后遍历数组array，将所有的元素复制到待返回的数组中，遇到奇数我们用下标x，遇到偶数我们用下标y。 （这种方法其实保证了相对位置不变）

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        int n = array.size();
        vector<int> res(n);
        int odd = 0; //统计奇数个数
        for(int i = 0; i < n; i++){ //遍历统计
            if(array[i] % 2)
                odd++;
        }
        int x = 0, y = odd; //x与y分别表示答案中奇偶数的坐标
        for(int i = 0; i < n; i++){
            if(array[i] % 2){ //奇数在前
                res[x] = array[i];
                x++;
            }else{ //偶数在后
                res[y] = array[i];
                y++;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组的长度，遍历2次数组
• 空间复杂度：$O(1)O(1)$，res数组属于返回函数必要数组，不算额外空间

方法二：交换法

具体做法：

利用左右双指针分别从数组首尾出发向中间走，交换其中的偶数在前奇数在后的情况，具体操作：如果左右都是奇数，说明左边没问题，因为奇数要在左边，因此左指针右移，右指针暂时不动；如果左奇数右偶数，符合要求，左右指针都向中间走；如果左偶数右奇数，符合要交换的条件，将偶数换到后面，奇数换到前面；如果左右都是偶数，只移动右指针，右边是偶数一定正确，指针左移，但是左边需要待定，于是暂时不动。

两指针相遇时就一定能保证左指针以左一定是奇数，右指针以右一定是偶数，做到了调整数组顺序使奇数位于偶数前面。（该方法不能保证相对位置不变）

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        int i = 0;
        int j = array.size() - 1; //双指针
        while(i < j){ //向中间聚合
            if(array[i] % 2 == 1 && array[j] % 2 == 1) //左右都是奇数，左移右不动
                i++;
            else if(array[i] % 2 == 1 && array[j] % 2 == 0) //左奇数右偶数，左右都向中间缩
                i++, j--;
            else if(array[i] % 2 == 0 && array[j] % 2 == 1) //左偶右奇数
                swap(array[i], array[j]); //交换
            else //左右都是偶数，只移动右指针
                j--;
        }
        return array;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为数组的长度，双指针最多只遍历数组一次
• 空间复杂度：$O(1)O(1)$，常数级变量无额外空间