剑指offer面试题21：调整数组顺序使奇数位于偶数前面

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

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

class Solution {
public:
    vector exchange(vector& nums)
    {
        int len = nums.size();  //数组大小
        vector res(len);
        int j = 0;
        for(int i = 0; i < len; i++)
        {
            if(nums[i] % 2)
            {
                res[j++] = nums[i];
            }
        }
        for(int i = 0; i < len; i++)
        {
            if(nums[i] % 2 == 0)
            {
                res[j++] = nums[i];
            }
        }
        return res;
    }
};

class Solution {
public:
    vector exchange(vector& nums)
    {
        int len = nums.size();  //数组大小
        vector res;
        for(int i = 0; i < len; i++)
        {
            if(nums[i] % 2)
            {
                res.push_back(nums[i]);
            }
        }
        for(int i = 0; i < len; i++)
        {
            if(nums[i] % 2 == 0)
            {
                res.push_back(nums[i]);
            }
        }
        return res;
    }
};

class Solution {
public:
    vector exchange(vector& nums)
    {
        int len = nums.size();  //数组大小
        vector res,oushu;
        for(int i = 0; i < len; i++)
        {
            if(nums[i] % 2)
            {
                res.push_back(nums[i]); //全是奇数
            }
            else
            {
                oushu.push_back(nums[i]); //全是偶数
            }
        }

        //将偶数数组插入奇数数组的尾部
        for(int j = 0; j < oushu.size(); j++)
        {
            res.push_back(oushu[j]);
        }      

        return res;
    }
};

class Solution {
public:
    vector exchange(vector& nums)
    {
        //双指针
        int left = 0;
        int right = nums.size() - 1;
        
        while(left <= right)
        {
            if(nums[left] % 2 == 1) left++;
            else if(nums[right] % 2 == 0) right--;
            else 
            {
                swap(nums[left],nums[right]);
                left++;
                right--;
            }
        }
        return nums;
    }
};

解题思路：
考虑定义双指针 left, right 分别指向数组左右两端，循环执行：

1、指针 left 从左向右寻找偶数；
2、指针 right 从右向左寻找奇数；
3、将 偶数 nums[left] 和 奇数 nums[right]  交换。
可始终保证： 指针 left 左边都是奇数，指针 right 右边都是偶数 。

算法流程：
1、初始化： left, right 双指针，分别指向数组 nums 左右两端；
2、循环交换： 当 left = right 时跳出；
                        指针 left 遇到奇数则执行 left++ 跳过，直到找到偶数；
                        指针 right 遇到偶数则执行 right-- 跳过，直到找到奇数；
                        交换 nums[left] 和 nums[right] 值；
3、返回值： 返回已修改的 nums 数组。

class Solution {
public:
    vector exchange(vector& nums)
    {
        //双指针
        int left = 0;
        int right = nums.size() - 1;
        
        while(left < right)
        {
            //左指针 left 遇到奇数则执行 left++ 跳过，直到找到偶数；
            while(left < right && nums[left]%2 == 1) left++;
            //右指针 right 遇到偶数则执行 right-- 跳过，直到找到奇数
            while(left < right && nums[right]%2 == 0) right--;

            //左指针指向偶数，右指针指向奇数，交换两个指针
            swap(nums[left],nums[right]);
        }
        return nums;
    }
};