剑指Offer JZ13 调整数组顺序使奇数位于偶数前面 C++实现

题目描述

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

解题思路

方法一：原地调整

1、思路：使用两个指针i，j，首先令i指向数组首位，令j指向数组中的第一个奇数，然后将[i，j)中的偶数后移，将j先前指向的奇数插入i中，然后令i自增，令j指向下一个奇数，不断重复上述操作，就能完成求解。

2、代码：

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

3、复杂度：

时间复杂度：O()；

空间复杂度：O(1)。

方法二：辅助空间

1、思路：开辟两个辅助空间分别存储奇数和偶数，最后将他们赋值回原空间。

2、代码：

class Solution {
public:void reOrderArray(vector<int> &array) {vector<int> odd;vector<int> even;for (auto it = array.begin(); it != array.end(); it++) {if ((*it & 1) == 1)odd.push_back(*it);else even.push_back(*it);}array.clear();array.insert(array.end(), odd.begin(), odd.end());array.insert(array.end(), even.begin(), even.end());} 
};

3、复杂度：

时间复杂度：O(n)；

空间复杂度：O(n)。