题解 | #调整数组顺序使奇数位于偶数前面#
调整数组顺序使奇数位于偶数前面
http://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b
描述
这是一篇面对初级coder的题解。
知识点：队列 指针 排序
难度：二星
题解
题目：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
为了优化代码，思考如何判断奇数和偶数效率最高
if（x&1）这样应该只用一个指令周期就能完成判断 开始跳转——有对编译原理感兴趣的同学欢迎讨论
方法一：队列
比较直观的想法是用队列把数组复制一份
一个奇数队列一个偶数队列
整理好再放回原队列
#include <queue>
class Solution {
public:
vector<int> reOrderArray(vector<int>& array) {
queue<int> odd ;
queue<int> even ;
for(int i = 0 ; i <array.size() ;i++){ //第一次遍历，存入两个队列
if(array[i]&1)
odd.push(array[i]);
else
even.push(array[i]);
}
int len_odd=odd.size();
int len_even=even.size();
int i;
for(i = 0 ; i <len_odd ;i++){//第二次遍历，从奇数队列中存入原数组
array[i]=odd.front();
odd.pop();
}
for(; i <array.size() ;i++){//第二次遍历，从偶数队列中存入原数组
array[i]=even.front();
even.pop();
}
return array;
}
};
<array.size>
</array.size> 显然，这样执行效率不高
运行时间： 13 ms 占用内存：1576K
时间复杂度O(2n)
空间复杂度O(n)
方法二：冒泡排序的思想
利用冒泡排序的思想，找到奇数就排到前面
class Solution {
public:
vectorreOrderArray(vector& array) {
int odd_num=0;//奇数记录
int cur_num;
int i,j;
for(i=0;i<array.size>=odd_num;j--)
array[j]=array[j-1];
array[odd_num]=cur_num;
odd_num++;
}
}
return array;
}
};</array.size> 运行时间： 125 ms 占用内存：1552K 时间复杂度：O(n2)，同冒泡排序
空间复杂度：O(1)
总结
排序题的扩展考法
需要熟悉经典的排序方法
排序算法的时间和空间不可兼得，
阿Q的题解 文章被收录于专栏
阿Q秋招刷过的题
