調整數組順序使奇數位于偶數前面（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%的使用者