[LeetCode] 922. Sort Array By Parity II 按奇偶排序数组之二

Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]Output: [4,5,2,7]Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

1. 2<=A.length<=20000
2. A.length%2==0
3. 0<=A[i]<=1000

这道题是之前那道 Sort Array By Parity 的拓展，那道让把奇数排在偶数的后面，而这道题是让把偶数都放在偶数坐标位置，而把奇数都放在奇数坐标位置。博主最先想到的方法非常简单粗暴，直接分别将奇数和偶数提取出来，存到两个不同的数组中，然后再把两个数组，每次取一个放到结果 res 中即可，参见代码如下：

解法一：

class Solution {public:    vector<int> sortArrayByParityII(vector<int>& A) {        vector<int> res, even, odd;        for (int num : A) {            if (num % 2 == 0) even.push_back(num);            else odd.push_back(num);        }        for (int i = 0; i < even.size(); ++i) {            res.push_back(even[i]);            res.push_back(odd[i]);        }        return res;    }};

论坛上还有一种更加简单的方法，不需要使用额外的空间，思路是用两个指针，i指针一直指向偶数位置，j指针一直指向奇数位置，当 A[i] 是偶数时，则跳到下一个偶数位置，直到i指向一个偶数位置上的奇数，同理，当 A[j] 是奇数时，则跳到下一个奇数位置，直到j指向一个奇数位置上的偶数，当 A[i] 和 A[j] 分别是奇数和偶数的时候，则交换两个数字的位置，从而满足题意，参见代码如下：

解法二：

class Solution {public:    vector<int> sortArrayByParityII(vector<int>& A) {        int n = A.size(), i = 0, j = 1;        while (i < n && j < n) {            if (A[i] % 2 == 0) i += 2;            else if (A[j] % 2 == 1) j += 2;            else swap(A[i], A[j]);        }        return A;    }};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/922

类似题目：

Sort Array By Parity

参考资料：

https://leetcode.com/problems/sort-array-by-parity-ii/

https://leetcode.com/problems/sort-array-by-parity-ii/discuss/181160/Java-two-pointer-one-pass-inplace

https://leetcode.com/problems/sort-array-by-parity-ii/discuss/193854/Linear-pass-using-2-pointers-in-C%2B%2B.

https://leetcode.com/problems/sort-array-by-parity-ii/discuss/181158/C%2B%2B-5-lines-two-pointers-%2B-2-liner-bonus

LeetCode All in One 题目讲解汇总(持续更新中...)