905.按奇偶排序数组

caution

原题链接：https://leetcode-cn.com/problems/sort-array-by-parity/submissions/

思路

暴力：

可以暴力模拟，先把奇数和偶数抽出来放到两个数组，然后分别排序（也许都不用排序），然后再合并。但是空间复杂度比较高。

优化方案：

双指针，从左往右找第一个不是偶数的，从右往左找第一个不是奇数的，然后交换。（类似快排的思想）

代码

暴力：

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        vector<int> odd, even;

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] % 2 == 0) odd.push_back(nums[i]);
            else even.push_back(nums[i]);
        }

        for (int i = 0; i < even.size(); i++) {
            odd.push_back(even[i]);
        }
        return odd;
    }
};

双指针：

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;

        while (l < r) {
            while (l < r && nums[l] % 2 == 0) l++;
            while (l < r && nums[r] % 2 != 0) r--;
            if (l < r && nums[l] % 2 != 0 && nums[r] % 2 == 0) {
                swap(nums[l], nums[r]);
                l++, r--;
            }
        }
        return nums;
    }
};