题解 | #调整数组顺序使奇数位于偶数前面(二)#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArrayTwo(vector<int>& array) {
        // 前后双指针，只需一次遍历，时间O(n)，空间O(1)
        int i = 0; 
        int j = array.size()-1;
        while(i<j){
            while(i<j && array[i]&1) i++;// arr[i]为奇数，i++向右移动，直到arr[i]为偶数
            while(i<j && (array[j]&1)==0) j--;// arr[j]为偶数，j--向左移动，直到arr[j]为奇数
            if(i<j) swap(array[i],array[j]);
        }
	  
	  // // 在原数组上遍历修改，时间O(n^2),空间O(1)
        // for(int i=0;i<array.size();i++){
        //     if(array[i]&1) continue;// 奇数不需要动
        //     else{// 若碰到偶数
        //         // 遍历之后的元素，找到第一个奇数
        //         bool flag = false;// 是否找到奇数
        //         for(int j=i+1;j<array.size();j++){
        //             if(array[j]&1){// 找到奇数
        //                 // 将奇偶元素交换，保证奇在偶前面
        //                 swap(array[i],array[j]);
        //                 flag = true;
        //                 break;
        //             }
        //         }
        //         // 如果偶数后面没有奇数，说明调整完毕，结束外层循环
        //         if(!flag) break;
        //     }
        // }
	  
        return array; 
    }
};