XTAO's Tech Blog
0%

[Leetcode]905. Sort Array By Parity (C++)

发表于 更新于 分类于 评论数：
830 1 分钟

题目描述

题目链接：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.

You may return any answer array that satisfies this condition.

例子

Input:[3,1,2,4]
Output: [2,4,3,1]
Explanation: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

解题思路

这道题目比较简单，可以创建一个和 A 等长的数组；遍历一遍 A，遇到奇数从后往前填入，遇到偶数从前往后填入即可。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>

class Solution {
public:
    std::vector<int> sortArrayByParity(std::vector<int>& A) {
        std::vector<int> results(A.size(), 0);
        int front = 0, back = A.size() - 1;
        for (int num: A) {
            if (num % 2 != 0) {
                // odd
                results[back] = num;
                back--;
            } else {
                // even
                results[front] = num;
                front++;
            }
        }

        return results;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n) —- 输出答案需要线性空间

推荐文章