剑指offer - 调整数组顺序使奇数位于偶数前面

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/beb5aa231adc45b2a5dcc5b62c93f593

题意

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

题解

插入排序的思想，从前往后扫描，遇到偶数则往后寻找下一个奇数，然后将奇数调整到这些偶数的前面，最坏情况下，就是前半部分全为偶数，后半部分全为奇数，时间复杂度O(N*N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        for(int i=0;i<array.size();i++){
            if(array[i]%2==0){
                int j=i+1;
                while(j<array.size()&&array[j]%2==0) j++;
                if(j==array.size()) break;
                int val = array[j];
                for(int k=j;k>i;k--)
                    array[k]=array[k-1];
                array[i]=val;
            }
        }
    }
};

发现一个STL方法，stable_partition，依据条件稳定划分，两组元素各维持相对顺序，即划分后，各组中元素的先后关系保持不变。
至于复杂度：

1
2
If enough extra memory is available, linear in the distance between first and last: Applies pred exactly once to each element, and performs up to that many element moves.
Otherwise, up to linearithmic: Performs up to N*log(N) element swaps (where N is the distance above). It also applies pred exactly once to each element.
1
2
3
4
5
6
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        stable_partition(array.begin(),array.end(),[](int x){return x%2;});
    }
};

当然可以用空间换时间，新建一个数组，从前往后扫描一遍，将奇数放到前面，然后从后往前扫一遍，将偶数放到后面，随后复制回去。