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

题目主要信息:

• 给定一个长度为n的无序数组，需要将其中的奇数放到数组前面，偶数放到数组后面
• 且调整后原来的奇数与奇数之间，偶数与偶数之间的相对位置不能改变

具体思路:

既然要把所有的奇数放在数组前面，所有的偶数放在数组后面，那可以统计奇数在原数组中出现了多少次，这样就可以找到二者的分界线。

• step 1：遍历数组，统计奇数出现的次数，即找到了偶数开始的位置。
• step 2：准备一个和原数组同样长的新数组承接输出，准备双指针，x指向奇数开始的位置，y指向偶数开始的位置。
• step 3：遍历原数组，遇到奇数添加在指针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数组属于返回必要空间，不属于额外空间