题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

数据范围

数组长度 $[0,100]$。

样例

输入：[1,2,3,4,5]
输出: [1,3,5,2,4]

NO.1 暴力

开一个新的数组，遍历两边给定数组，分别把奇数和偶数给放进去。

代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> v;
        //第一遍：奇数
        for (int i = 0; i < array.size(); i ++)
            if (array[i] & 1)
                v.push_back(array[i]);
        //第二遍：偶数
        for (int i = 0; i < array.size(); i ++)
            if ((array[i] & 1) == 0)
                v.push_back(array[i]);
        //copy回去
        array = v;
    }
};

NO.2 双指针

开两个指针$i、j$，$i$指向数组的第一个数，$j$指向数组的最后一个数，然后两个指针分别往中间走。
$i$指针走到偶数时停下，$j$指针走到奇数时停下，然后把两个指针对应的数交换，再继续重复，直到$i>=j$时为止。

代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int i = 0, j = array.size() - 1;
        while (i < j)
        {
            while (array[i] % 2 == 1)
                i ++;
            while (array[j] % 2 == 0) 
                j --;
            if (i < j)
                swap(array[i], array[j]);
        }
    }
};

好了，这篇题解到这里就结束了，感谢观看，祝各位$RP++$。

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$