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

描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

算法

题目要求图解：

具体的做法就是把每个数加入符合条件的数组，如下图，橙色代表奇数数组，绿色代表偶数数组，最后再合并两个数组。

因为我们是按照从左到右的顺序访问每个元素，容易证明奇数元素、偶数元素之间的相对位置是可以保证的，实现的代码如下：

// c++
class Solution {
public:
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        vector<int> l, r;
        for (int c : array) {
            if (c % 2) l.emplace_back(c);
            else r.emplace_back(c);
        }
        l.insert(l.end(), r.begin(), r.end());
        return l;
    }
};

python中可以直接使用重载的 + 运算符合并两个 list :

# python3
class Solution:
    def reOrderArray(self , array ):
        # write code here
        l1, l2 = [], []
        for each in array:
            if each % 2: l1.append(each)
            else: l2.append(each)
        return l1 + l2

不用合并数组的解法

思路类似，不过是遍历两次数组，第一次挑出奇数元素，第二次挑出偶数元素：

// c++
class Solution {
public:
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        vector<int> res(array.size(), 0);
        int idx = 0;
        for (int u : array)
            if (u % 2) res[idx++] = u;
        for (int u : array)
            if (u % 2 == 0) res[idx++] = u;
        return res;
    }
};

python代码如下

# python3
class Solution:
    def reOrderArray(self , array ):
        # write code here
        res = []
        for each in array:
            if each % 2: res.append(each)
        for each in array:
            if not each % 2: res.append(each)
        return res

因为两次遍历数组时间复杂度是 O(n)，使用了一个额外数组空间复杂度是 O(n)