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

题目描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序。

使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。

样例

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

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

算法1

(双指针扫描)

用两个指针分别从首尾开始，往中间扫描。扫描时保证第一个指针前面的数都是奇数，第二个指针后面的数都是偶数。
每次迭代时需要进行的操作：

1. 第一个指针一直往后走，直到遇到第一个偶数为止；
2. 第二个指针一直往前走，直到遇到第一个奇数为止；
3. 交换两个指针指向的位置上的数，再进入下一层迭代，直到两个指针相遇为止；

C++ 代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int l = 0, r = array.size() - 1;
        while( l < r)
        {
            //奇数往后移动指针
            while( l < r && array[l] % 2 == 1 ) l++;
            while( l < r && array[r] % 2 == 0 ) r--;
            //此时l指向的是偶数，r指向的为奇数，交换两个数字
            if( l < r) swap(array[l], array[r]);
        }
    }
};

算法2

(开辟额外空间存储)

用vector数组来存储扫描中的偶数，最后在赋值给原数组；

C++ 代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        vector<int> temp;
        
        int j = 0;
        for(int i = 0; i < array.size(); i ++)
        {
            if(array[i] % 2 == 1 ) array[j++] = array[i];
            else temp.push_back(array[i]);
        }
        
        for(int i = j, k = 0; i < array.size(); i ++) array[i] = temp[k++];
    }
};