题目描述：

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

数据范围：0≤n≤50000，数组中每个数的值 0 ≤val≤10000
要求：时间复杂度 O(n)，空间复杂度 O(1) 示例1 输入： [1,2,3,4]
返回值： [1,3,2,4]
说明： [3,1,2,4]或者[3,1,4,2]也是正确答案

题解1：双指针

1. 定义双指针，left指向最左边，right指向数组最右边
2. 当left < right 时，用while寻找最左边的偶数和寻找最右边的奇数
3. while(array[left] & 1 == 1)当left指向的数是奇数时，left++，指向下一个数值，直至指向偶数
4. while(array[right] & 1 == 0)当right指向的数是偶数时，right--，指向下一个数值，直至指向奇数
5. 当left < right 时，交换

图示来自代码届的小白

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArrayTwo(vector<int>& array) {
        // write code here
        //双向队列法
//         deque<int> de;
//         for(int i:array){
//             if(i & 1 == 1)//奇数
//                 de.push_front(i);
//             else
//                 de.push_back(i);
//         }
//         vector<int> v;
//         for(int i = 0;i< de.size();i++){
//             v.push_back(de[i]);
//         }
//         return v;
        //双指针法
        if(array.size() < 2 ) return array;
        int l =0,r = array.size() - 1;
        while(l < r){
            while((array[l]&1) == 1) l++;//找到奇数
            while((array[r]&1) == 0) r--;//找到偶数
            if(l<r){
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;                
            }
        }
        return array;
    }
};