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

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


分析

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

代码如下:


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函数,从原数组的两端向中间扫描,前、后指针分别遇到偶数和奇数就停下来,然后交换他们即可。

代码如下:


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上:点我前往