题目描述

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

https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

题解

新建一个数组存储答案，遍历两次数组，一次找奇数，一次找偶数。

或者双指针（相向指针）从前往后在奇数部分找偶数，同时从后往前在偶数部分找奇数。

也可以双指针原地交换。

双指针

class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int odd_ptr = nums.size() - 1;    // 从后往前遍历，寻找偶数中的奇数
        int even_ptr = 0;                 // 从前往后遍历，寻找奇数中的偶数
        while (even_ptr < odd_ptr) {
            while (even_ptr < odd_ptr && nums[even_ptr] % 2)
                ++even_ptr;
            while (even_ptr < odd_ptr && nums[odd_ptr] % 2 == 0)
                --odd_ptr;
            if (even_ptr < odd_ptr)
                swap(nums[odd_ptr--], nums[even_ptr++]);
        }
        return nums;
    }
};