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:
2 <= A.length <= 20000A.length % 2 == 00 <= 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
类似题目：
参考资料：
https://leetcode.com/problems/sort-array-by-parity-ii/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
