[LeetCode] 905. Sort Array By Parity

[grandyang]

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:

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

这道题让我们给数组重新排序，使得偶数都排在奇数前面，并不难。最直接的做法就是分别把偶数和奇数分别放到两个数组中，然后把奇数数组放在偶数数组之后，将拼接成的新数组直接返回即可，参见代码如下：
解法一：

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
		vector<int> even, odd;
		for (int num : A) {
			if (num % 2 == 0) even.push_back(num);
			else odd.push_back(num);
		}
		even.insert(even.end(), odd.begin(), odd.end());
		return even;
    }
};

我们也可以优化空间复杂度，不新建额外的数组，而是采用直接交换数字的位置，使用两个指针i和j，初始化均为0。然后j往后遍历，若遇到了偶数，则将 A[j] 和 A[i] 交换位置，同时i自增1，这样操作下来，同样可以将所有的偶数都放在奇数前面，参见代码如下：
解法二：

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

我们还可以使用 STL 的内置函数 partition，是专门用来给数组重新排序的，不过我们要重写排序方式，将偶数的都放在前面即可，参见代码如下：
解法三：

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
		partition(A.begin(), A.end(), [](auto a) { return a % 2 == 0; });
		return A;
    }
};

Github 同步地址:

#905

参考资料：

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

https://leetcode.com/problems/sort-array-by-parity/discuss/170734/C%2B%2BJava-In-Place-Swap

https://leetcode.com/problems/sort-array-by-parity/discuss/170725/Know-your-C%2B%2B-Algorithms!-This-is-std%3A%3Apartition-%3A)

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