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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        if(array.empty())return vector<int>();

        //类似与插入排序
        int l = -1;
        int r = 0;
        while(r < array.size()){
            if(array[r] % 2 == 1){

                int tmp = array[r];
                for(int i = r;i > l + 1;i -= 1){
                    array[i] = array[i - 1];
                }
                l += 1;
                array[l] = tmp;
            }
            r += 1;
        }
        return array;
    }
};

题解二：不使用额外的空间，使用双指针，一个指针负责指明奇数的范围，一个指针负责寻找奇数，在一开始的时候，指向奇数范围的指针必须先是-1，这方便以后的判断，如果负责寻找奇数的指针找到了奇数，首先先将两个指针之间的数据都向右移动一位，然后将原先右指针指向的奇数放入左指针的下一个位置，然后奇数范围扩张。时间复杂度是O(n * n),空间复杂度是O(1)。有点类似于插入排序吧。

class Solution {
vector<int> reOrderArray(vector<int>& array) {
        // write code here
        if(array.empty())return vector<int>();
        //偶数
        vector<int> tmp1;
        //奇数
        vector<int> tmp2;
        for(int i = 0;i < array.size();i++){
            if(array[i] % 2 == 0)tmp1.push_back(array[i]);
            else tmp2.push_back(array[i]);
        }
        if(tmp1.empty())return tmp2;
        if(tmp2.empty())return tmp1;

        for(int i = 0;i < tmp1.size();i += 1){
            tmp2.push_back(tmp1[i]);
        }
        return tmp2;
    }
 

题解一：通过分离出数组的奇数和偶数，然后将偶数数组的元素都压入奇数队列，最后返回奇数队列即可，时间复杂度是O(n)，空间复杂度是O(n)。