题面

输出一个整数数组，实现一个函数来调整该数组中数字的程序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半局部。

示例：

输出：nums = [1,2,3,4]
输入：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

提醒：

0 <= nums.length <= 50000
1 <= nums[i] <= 10000

原题链接

剖析

刚开始想到思路 1：

从前向后遍历数组，遇到奇数时，什么也不做；遇到偶数时，把该偶数删除，而后把该偶数放到数组前面

然而这种思路会 超时

上面剖析超时起因：

数组最大长度为 50000，思路 1 绝不仅仅是简略的遍历数组，工夫复杂度为 O(N)，思路 1 还波及到数组的插入、删除，删除操作（erase）的复杂度就是 O(N)，最坏状况下，工夫复杂度为 O(N2)，太大。

接下来想到思路 2：

采纳双指针，left 指向数组首部，right 指向数组尾部，left 总体趋势向右挪动，right 总体趋势向左挪动

上面剖析这种思路不超时的起因：

只遍历数组一遍，工夫复杂度为 O(N)。

源代码（正文局部即为思路）

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {int len =  nums.size();
        int left = 0;
        int right = len-1;
        while(left<right){
            // 左偶、右奇
            if(nums[left]%2==0 && nums[right]%2==1){// 替换数组元素的操作其实很简略，工夫复杂度 O(1)，空间复杂度 O(1)
                int tmpL = nums[left];
                int tmpR = nums[right];
                nums[left] = tmpR;
                nums[right] = tmpL;
                left++;
                right--;
            }
            // 左偶、右偶
            if(nums[left]%2==0 && nums[right]%2==0){right--;}
            // 左奇、右偶
            if(nums[left]%2==1 && nums[right]%2==0){
                left++;
                right--;
            }
            // 左奇、右奇
            if(nums[left]%2==1 && nums[right]%2==1){left++;}

        } 
        return nums;
    }
};

提交后果：