题目的主要信息：

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

方法一：双指针复制法

具体做法：

可以准备一个待返回的长度为$nn$的数组，我们先遍历数组array找到其中的奇数有多少个，然后准备两个起始坐标，x表示奇数的起始坐标从0开始，y表示偶数的起始坐标，从刚刚找到的奇数个数开始，然后遍历数组array，将所有的元素复制到待返回的数组中，遇到奇数我们用下标x，遇到偶数我们用下标y。

class Solution {
public:
    vector<int> reOrderArray(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)$，两次单独的遍历
• 空间复杂度：$O(1)O(1)$，res数组属于返回函数必要数组，不算额外空间

方法二：两次复制法

具体做法：

我们可以准备一个空的待返回函数，遍历两次原数组，第一次将奇数push进数组，第二次再将偶数push进数组。

class Solution {
public:
    vector<int> reOrderArray(vector<int>& array) {
        vector<int> res;
        for(int i = 0; i < array.size(); i++) 
            if(array[i] % 2) //遍历数组先将遇到的奇数加入
                res.push_back(array[i]);
        for(int i = 0; i < array.size(); i++)
            if(array[i] % 2 == 0) //遍历数组再将遇到的偶数加入
                res.push_back(array[i]);
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，两次单独的遍历
• 空间复杂度：$O(1)O(1)$，res数组属于返回函数必要数组，不算额外空间