调整数组顺序使奇数位于偶数前面（C++简单区）

调整数组顺序使奇数位于偶数前面

题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4]

输出：[1,3,2,4]

注：[3,1,2,4] 也是正确的答案之一。

提示：

1 <= nums.length <= 50000

1 <= nums[i] <= 10000

解题思路一

暴力解法

算法流程：

1. 从头开始遍历，将遍历到的奇数放在另一个vector数组中
2. 将当前奇数从原始容器中删除
3. 将当前迭代器回指一位（因为erase执行完后返回的是删除元素的后一位（- -操作是为了防止越界））
4. 循环上述操作直到遍历完原始容器
5. 将原始容器中剩余的元素（所剩的皆为偶数）插入到新容器的末尾

代码如下（示例）：

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        vector<int>v;
        for(vector<int>::iterator it=nums.begin();it!=nums.end();it++)
        {
            if(*it%2!=0)
            {
                //当前元素为奇数就放入v容器中
                v.push_back(*it);
                //在当前容器中删除此元素
                nums.erase(it);
                //此处减一是因为erase执行完后返回的是删除元素的后一位（--是为了防止越界）
                it--;
            }
        }
        if(nums.empty()) return v;
        else
        {
            v.insert(v.end(),nums.begin(),nums.end());
            return v;
        }
    }
};
执行用时：1320 ms, 在所有 C++ 提交中击败了5.84%的用户
内存消耗：18.6 MB, 在所有 C++ 提交中击败了7.18%的用户
           

结论：上述方法不论时间还是空间效果都极差。

解题思路二

首尾双指针法

算法流程：

1. 定义两个指针，让它们分别指向容器的头和尾
2. 头指针循环找到容器中第一个偶数
3. 尾指针循环找到容器中第一个奇数
4. 将奇数和偶数交换在容器中的位置
5. 重复2、3、4步直到两指针会合结束循环

代码如下：

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
       if(nums.empty()||nums.size()==1) return nums;
       int n=nums.size();
       int i=0,j=n-1;
       while(i<j)
       {
           //从前往后找到第一个偶数
            while(i<j && (nums[i]&1)!=0) i++;
            //从后往前找到第一个奇数
            while(i<j && (nums[j]&1)==0) j--;
            将这两个奇数和偶数交换
            if(i<j)
            {
                int tem=nums[i];
                nums[i]=nums[j];
                nums[j]=tem;
            }
        }
    return nums;
    }
};
执行用时：40 ms, 在所有 C++ 提交中击败了85.99%的用户
内存消耗：17.7 MB, 在所有 C++ 提交中击败了74.78%的用户
           

解题思路三

快慢指针法

算法流程：

1. 定义两个快慢指针，让它们同时指向容器的头部
2. 快指针开始遍历容器找到容器中第一个奇数
3. 当快指针找到奇数时将它于慢指针所指元素交换，同时移动慢指针指向下一位
4. 交换完后让快指针继续遍历找到奇数，，然后继续与慢指针所指元素交换，直找到容器末尾结束

代码如下：

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
       if(nums.empty()||nums.size()==1) return nums;
       int fast=0,low=0;
       while(fast<nums.size())
       {
           if((nums[fast]&1)!=0)
           {
               swap(nums[fast],nums[low]);
               low++;
           }
           fast++;
       }
       return nums;
    }
};
执行用时：40 ms, 在所有 C++ 提交中击败了85.99%的用户
内存消耗：17.6 MB, 在所有 C++ 提交中击败了94.31%的用户