题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

此算法保证了相对次序不变

C++ 代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.size() <= 1) return ;
        for(int i = 0; i < array.size();i++){
            for(int j = array.size() -1 ; j>i;j--){
                if(array[j]%2 == 1 && array[j -1]%2 ==0)
                swap(array[j],array[j-1]);
            }
        }
    }
};

算法2

(双指针) $O(n)$

此算法保证不了位置是相对的

每次迭代时需要进行的操作：

• 第一个指针一直往后走，直到遇到第一个偶数为止；
• 第二个指针一直往前走，直到遇到第一个奇数为止；
• 交换两个指针指向的位置上的数，再进入下一层迭代，直到两个指针相遇为止；

C++ 代码

class Solution {
public:
    void reOrderArray(vector<int> &array) {
         int l = 0, r = array.size() - 1;
         while (l <= r) {
             while (array[l] % 2 == 1) l ++ ;
             while (array[r] % 2 == 0) r -- ;
             if (l < r) swap(array[l], array[r]);
         }
    }
};