Problem
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:
1 2 3 |
<strong>Input: </strong><span id="example-input-1-1">[3,1,2,4]</span> <strong>Output: </strong><span id="example-output-1">[2,4,3,1]</span> The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. |
Note:
1 <= A.length <= 5000
0 <= A[i] <= 5000
Solution 1: Split Odd/Even
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 44 ms class Solution { public: vector<int> sortArrayByParity(vector<int>& A) { vector<int> even; vector<int> odd; for (int a : A) { if (a % 2) odd.push_back(a); else even.push_back(a); } even.insert(end(even), begin(odd), end(odd)); return even; } }; |
Solution 2: Stable sort by key % 2
Time complexity: O(nlogn)
Space complexity: O(1) in-place
C++
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua, 52 ms class Solution { public: vector<int> sortArrayByParity(vector<int>& A) { stable_sort(begin(A), end(A), [](int a, int b){ return a % 2 < b % 2; }); return A; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment