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


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation