这道题在牛客网中增加了难度，要求偶数和偶数之间的相对位置不变，而书中的解法会出现相对位置改变的问题，所以应该进行改进。
改进的思路和插入排序很像。从左到右，先找到一个偶数，然后在偶数后面去寻找一个奇数。如果找到了这个奇数，就去当前偶数和奇数之间的数字都向右移动一位，然后将奇数插入到移位后空出来的最前面。
因为题目直接引用传入了一个 vector，所以用空间换时间再加一个新的 vector 的思路可能不太符合题意。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
void reOrderArray(vector<int> &array) {
int len=(int)(array.size());
if(len<=0) return;
int pEven=0;
int pOdd;
while(pEven<len){
while(pEven<len && (array[pEven]&1)!=0) pEven++;
pOdd=pEven+1;
while(pOdd<len && (array[pOdd]&1)==0) pOdd++;
if(pOdd<len){
int t=array[pOdd];
for(int i=pOdd;i>pEven;i--){
array[i]=array[i-1];
}
array[pEven]=t;
}else break;
}
}
};
|