剑指offer 调整数组顺序使奇数位于偶数前面
- 题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
- 解法一
如果是要保证时间上最快的话，申请两个queue，分别保存奇偶数，完了再放回原数组就ok了。
class Solution {
public:
void reOrderArray(vector<int> &array) {
queue<int> odd;
queue<int> even;
int size = array.size();
for (int i = 0; i < size; ++i){
if (array[i] % 2 == 0){
even.push(array[i]);
}
else{
odd.push(array[i]);
}
}
int osize = odd.size();
int esize = even.size();
for (int i = 0; i < osize; ++i){
array[i] = odd.front();
odd.pop();
}
for (int i = 0; i < esize; ++i){
array[osize + i] = even.front();
even.pop();
}
}
};
- 解法二
申请一个vector，保存原始array的元素。从vector的左侧向右遍历，遇到奇数则放到array中；同时从vector的右侧向左遍历，遇到偶数则放到array的末尾。遍历完就得到了需要的结果，这样可以保证相对位置不变。
class Solution {
public:
void reOrderArray(vector<int> &array) {
vector<int> temp(array);
int size = array.size();
int lcount = 0;
int rcount = 0;
for (int i = 0, j = size - 1; i < size, j >= 0; i++, j--){
if (temp[i] % 2 == 1){
array[lcount++] = temp[i];
}
if (temp[j] % 2 == 0){
array[size - rcount - 1] = temp[j];
rcount++;
}
}
}
};