维护一个标记firstEven指向数组当前第一个偶数的位置。
遍历数组,当遇到一个奇数时,判断其下标与firstEven是否相等,若相等,说明目前数组前面都是奇数,不需要调整顺序,使firstEven++,保持与循环控制遍历i同步。若不等,说明前面已有偶数出现,将当前i指向的奇数插入firstEven指向的位置,这里插入为了维持数组的稳定,即偶数与奇数内部的顺序不变,采用类似插入排序的方式,firstEven到i-1之前的偶数整体后移1位。当遇到偶数时,空过。
这种方式采用原地操作,空间复杂度为O(1)。由于有循环嵌套,时间复杂度大于O(n),具体情况根据输入数组的情况改变。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> reOrderArray(vector<int>& array) {
// write code here
int firstEven = 0;
for(int i = 0;i < array.size();i++){
if(array.at(i) % 2 && i == firstEven){
firstEven++;
}
else if(array.at(i) % 2){
int temp = array.at(i);
int pre = array.at(firstEven);
for(int j = firstEven + 1;j < i + 1;j++){
int tmp = array.at(j);
array.at(j) = pre;
pre = tmp;
}
array.at(firstEven) = temp;
firstEven++;
}
}
return array;
}
};