辅助数组+双指针,同时从两头开始遍历。左边遍历的指针来检测奇数,遇到奇数往结果数组的前面放;右边的指针用来检测偶数,遇到偶数往结果数组的尾部放。时间复杂度O(n),空间复杂度O(n),思路简单,代码简单。

vector<int> reOrderArray(vector<int>& array) {
        // write code here
        int i = 0; 
        int j = array.size()-1;
        int indexi = i;
        int indexj = j;
        vector<int> res(array.size(),0);
        while(i<array.size() && j>= 0 && indexi <= indexj){
            if(array[i] & 1) res[indexi++] = array[i]; 
            if(!(array[j] & 1)) res[indexj--] = array[j];
            i++;
            j--;
        }
        return res;
}