[LeetCode] 905. Sort Array By Parity 按奇偶排序数组

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.html

You may return any answer array that satisfies this condition.git

Example 1:github

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，这样操做下来，一样能够将全部的偶数都放在奇数前面，参见代码以下：this

解法二：指针

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，是专门用来给数组从新排序的，不过咱们要重写排序方式，将偶数的都放在前面便可，参见代码以下：code

解法三：htm

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

Github 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中...)