题解 | #调整数组顺序使奇数位于偶数前面(二)#

题目的主要信息：

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是要求时间复杂度$O(n)O(n)$，空间复杂度$O(1)O(1)$。

方法一：

采用双指针遍历。left从左边开始遍历数组，right从右边开始遍历数组。首先left遍历一遍所有位于开头的奇数，直到当前数不是奇数时停下，然后right开始从后往前遍历素有的偶数，直到当前数字为奇数时停下。此时，如果left在right的左边，left所指的值为偶数，right所指的为奇数，需要进行交换，使得奇数位于偶数之前。然后继续重复以上操作。 具体做法：

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        if (array.empty()){
            return array;
        }
        int left = 0, right = array.size() - 1;//两个指针
        while (left < right){
            while (array[left] % 2 == 1){//遍历前面的所有奇数
                ++ left;
            }
            while (array[right] % 2 == 0){//遍历数组后面的所有偶数
                -- right;
            }
            if (left < right){//来到第一个需要交换的位置
                swap(array[left], array[right]);//交换奇数和偶数
            }
        }
        return array;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历一遍数组。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

用res向量保存结果，首先遍历一遍array，把其中的所有奇数放入res中，然后再遍历一遍array，把所有偶数放入res中，这样就能保证素有奇数在偶数之前。

具体做法：

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        int n = array.size();
        vector<int> res(n);
        int pos = 0;
        for(int i = 0; i < n; i++){//遍历一遍数组
            if(array[i] % 2){ //如果是奇数
                res[pos] = array[i];//放入res中
                pos++;
            }
        }
        for(int i = 0; i < n; i++){//遍历一遍数组
            if(array[i] % 2 == 0){ //如果是偶数
                res[pos] = array[i];//放入res中
                pos++;
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历数组。
• 空间复杂度：$O(n)O(n)$，res数组的大小为n。