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

ryluo 2020-06-27 12:42:25

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

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

样例

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

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

分析:

双指针。一个从头开始,一个从尾开始,从头开始的保证前面都是奇数,从尾开始的保证后面都是偶数,如果头部遇到了偶数,尾部遇到了奇数,就相互交换。

注意:因为该题没有说明保证重新排列的奇数和偶数的相对位置需要保持一致,所以这里可以不用考虑相对位置。

详细题解:https://www.acwing.com/solution/content/738/

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int l = 0, r = array.size() - 1;

        while(l < r){
            if(array[l] % 2 == 1) l ++;
            if(array[r] % 2 == 0) r --;
            if(l < r) swap(array[l], array[r]); // 这里也需要有个判断,因为前面的l和r发生了变化
        }
    }
};

也可以借鉴快排模板:

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--;
            if (l < r) swap(array[l], array[r]);
        }
    }
};