面试题14:调整数组顺序使奇数位于偶数前面

题目:输入一个整数数组,实现一个函数来调整数组中数字的顺序,是得所有的奇数位于数组的前半部分,所有偶数位于数组的后半部分。


分析

最简单的办法就是开辟和原数组同样大小的空间,顺次扫描原数组2次,第一次将所有奇数放进新数组中,第二次将偶数放入就可以。这种方法的时间复杂度为O(n),空间复杂度为O(n)。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void ReorderOddEven(vector<int>& arr)
{
vector<int> newarr;
int i;
for(i=0;i<arr.size();++i)
{
if(arr[i]&0x1)
{
newarr.push_back(arr[i]);
}
}
for(i=0;i<arr.size();++i)
{
if(!(arr[i]&0x1))
{
newarr.push_back(arr[i]);
}
}
arr.clear();
arr=newarr;
}

以上算法的优点是不会改变原数据的相对顺序。我们也可以只扫描原数组一次,若为奇数,则从新数组前面开始往后放;若为偶数,则从新数组后面开始往前放。这种方法缺点是会使偶数的相对顺序翻转。代码从略。

一种更好的思路是,受快速排序算法的启发,我们模仿快速排序的partition函数,从原数组的两端向中间扫描,前、后指针分别遇到偶数和奇数就停下来,然后交换他们即可。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
void ReorderOddEven(vector<int>& arr)
{
int i=0,j=arr.size()-1;
while(i<j)
{
while(i<j && (arr[i] & 0x1))
i++;
while(i<j && !(arr[j] & 0x1))
j--;
swap(arr[i],arr[j]);
}
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往