个人技术分享

1. 题目

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

2. 示例

3. 分析

开辟一个数组res用来保存操作过后的元素。第一次遍历数组只插入偶数，第二次遍历数组只插入奇数。

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) 
        {
            if (num % 2 == 0) res.push_back(num[i]);
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (num % 2 == 1) res.push_back(num[i]);
        }
        return res;
    }
};

能不能只遍历一次数组？可以滴。遇到偶数，替换到res数组偶数区间，即左侧区间；遇到奇数，替换到res数组奇数区间，即右侧区间。

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        int left = 0, right = n - 1;
        for (int i = 0; i < n; i++) 
        {
            if (num[i] % 2 == 0) res[left++] = num[i];
            else res[right--] = num[i];
        }
        return res;
    }
};

前面两种方法都需新开辟一个数组，那能不能不开辟而是原地进行替换？那是可以滴。

定义两个指针，左指针跳过偶数寻找奇数，右指针跳过奇数寻找偶数，交换左右指针元素。

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int n = nums.size();
        int left = 0, right = n - 1;
        while(left < right)
        {
            while(left < right && nums[left] % 2 == 0) left++;
            while(left < right && nums[right] % 2 == 1) right--;
            swap(nums[left++], nums[right--]);
        }
        return nums;
    }
};

或者只用一个指针 j 用来表示元素为奇数。遍历数组寻找到偶数后，交换二者元素即可。思想上感觉都差不多=.= ，只是更简洁~~~

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int n = nums.size();
        int j = 0;
        for(int i = 0; i < n; i++)
        {
            if(nums[i] % 2 == 0) swap(nums[i], nums[j++]);
        }
        return nums;
    }
};