剑指offer(C++)

剑指offer(C++)"/>

剑指offer(C++)

作者：翟天保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;}
};