算法1
单独开两个数组用于存储奇数元素和偶数元素,最后合并,并copy给原数组
C++ 代码
class Solution {
public:
void reOrderArray(vector<int> &array) {
vector<int> A;
vector<int> B;
for(int i = 0;i<array.size();i++)
{
if(array[i]%2!=0)
{
A.push_back(array[i]);
}
else
B.push_back(array[i]);
}
for(int i = 0;i<B.size();i++)
{
A.push_back(B[i]);
}
array = A;
}
};
算法2
双指针算法,类似于快速排序的划分过程
C++ 代码
class Solution {
public:
void reOrderArray(vector<int> &array) {
int l = 0,r = array.size()-1;
if(l>=r)
return;
int i = -1,j = array.size();
while(i<j)
{
do i++; while(array[i]%2!=0);
do j--; while(array[j]%2==0);
if(i<j)
swap(array[i],array[j]);
}
}
};