剑指offer(C++)-JZ21：调整数组顺序使奇数位于偶数前面(一)(算法-其他)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

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

数据范围：0≤n≤5000，数组中每个数的值0≤val≤10000

要求：时间复杂度 O(n)，空间复杂度 O(n)

进阶：时间复杂度 O(n2)，空间复杂度 O(1)

示例：

输入：

[2,4,6,5,7]

返回值：

[5,7,2,4,6]

解题思路：

本题考察算法思维。两种解题思路：

1)定位法

       进行一次遍历，确认奇数数量；再次遍历，以奇数数量作为偶数开始放置的下标，完成分割线的定位；以0作为奇数开始放置的下标，再进行一次遍历即可，记得下标刷新。

2)分组法

       巧妙应用stable_partition函数和Lamda表达式，stable_partition函数是稳定的分组函数，通过Lamda表达式确认分组的要求，将奇数分一组，偶数分一组，分组后其相对位置也不变。

测试代码：

1)定位法

#include <vector>
class Solution {
public:
    // 重排序
    vector<int> reOrderArray(vector<int>& array) {
        int size = int(array.size());
        vector<int> result(size);
        // 统计奇数个数
        int odd = 0;
        for(int i = 0; i < size; ++i){
            if(array[i] % 2){
                odd++;
            }
        }
        // 放置数据
        int o = 0;
        int e = odd;
        for(int i = 0; i < size; ++i){
            if(array[i] % 2){
                result[o] = array[i];
                o++;
            }
            else{
                result[e] = array[i];
                e++;
            }
        }
        return result;
    }
};

2)分组法

#include <vector>
class Solution {
public:
    // 重排序
    vector<int> reOrderArray(vector<int>& array) {
        stable_partition(array.begin(), array.end(), [](int x){
            return x % 2 == 1;
        });
        return array;
    }
};