题目描述
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
思路
对于一个需要按顺序或者颠倒顺序的题,首先就应该想到使用队列或者栈来实现。(直接用两个数组实现也是一样)
本题需要按顺序,因此用2个队列来将所有奇数和偶数分开,再一次弹回即可。
实现:
class Solution {
public:
void reOrderArray(vector<int> &array) {
queue<int> q1;
queue<int> q2;
int s=array.size();
for (int i=0;i<s;i++)
{
if (array[i]&1)
{
q1.push(array[i]);
}
else
q2.push(array[i]);
}
int j=0;
while (!q1.empty())
{
array[j]=q1.front();
q1.pop();
j++;
}
while (!q2.empty())
{
array[j]=q2.front();
q2.pop();
j++;
}
}
};
时间复杂度和空间复杂度都是O(n)