题面

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

示例：

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

提醒：

0 <= nums.length <= 500001 <= 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;    }};

提交后果：