leetcode - 按奇偶排序数组

题目地址

题目描述

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案。

示例：

输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示：

1 <= A.length <= 5000
0 <= A[i] <= 5000

本题主要解决方案有如下两种：

1、多数组
声明奇数数组和偶数数组，一次遍历将数组拆分为奇数数组和偶数数组，最后合并数组进行返回。

    vector<int> sortArrayByParity(vector<int>& nums) {
        vector<int> result;
        vector<int> odd;   // 奇数数组
        vector<int> even; // 偶数数组
        for (int i = 0;i < nums.size();i++) {
            if (nums[i] % 2 == 0) {
                even.push_back(nums[i]);
            } else {
                odd.push_back(nums[i]);
            }
        }
        result.insert(result.end(), even.begin(), even.end());
        result.insert(result.end(), odd.begin(), odd.end());
        return result;
    }

2、双指针法
可以理解为数组左边为偶数，右边为奇数。通过左指针进行遍历碰到单数暂停，右指针进行遍历碰到偶数暂停。直到左右指针相遇。

    vector<int> sortArrayByParity(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            // 左指针指向偶数时向右‘前进’
            while (l < nums.size() && nums[l] % 2 == 0) {
                l++;
            }
            // 右指针指向奇数时向左‘前进’
            while (r >= 0 && nums[r] % 2 == 1) {
                r--;
            }
            if (l < r) {
                // 交换
                swap(nums[l], nums[r]);
            }
        }
        return nums;
    }