[LeetCode] 922. Sort Array By Parity II

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)