[LeetCode]905. Sort Array By Parity

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
字数统计：506 字 | 阅读时长：3 分钟

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.

Example 1:

1
2
3
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

题目解析：将奇偶数排序，偶数在前，奇数在后，偶/奇数内部无需关心排序；

方案一

思路：一个数组，遍历数组，新建一个vector用于返回，偶数在前面插入，奇数在后面插入；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        vector<int> out;
        for (const int item: A) {
            if (item % 2 == 0) {
                out.emplace(out.begin(), item);
            } else {
                out.emplace_back(item);
            }
        }
        return out;
    }
};

result

Runtime: 64 ms, faster than 10.14% of C++ online submissions for Sort Array By Parity.

Memory Usage: 9.9 MB, less than 98.71% of C++ online submissions for Sort Array By Parity.

执行时间太多了！怎么这么慢

方案二

  • 返回的数组大小也是固定的，初始化固定长度的vector；

  • 循环迭代的同时赋值，对应index++或者index—；

  • 其中 & 运算和 % 运算，从效率上来说并没有差别，换了之后也差不多；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        int len = A.size();
        vector<int> out(len);
        for (int i = 0, begin_out = 0, end_out = len - 1; i < len; i++) {
            if (A[i] & 1) {
                out[end_out--] = A[i];
            } else {
                out[begin_out++] = A[i];
            }
        }
        return move(out);
    }
};

result

Runtime: 28 ms, faster than 98.35% of C++ online submissions for Sort Array By Parity.

Memory Usage: 9.7 MB, less than 99.36% of C++ online submissions for Sort Array By Parity.

方案三

高手在民间，网友出绝招，讨论区的解决方案，效率上差不多，就是相当简洁。

1
2
3
4
5
6
7
8
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        auto is_even = [] (auto e) { return e % 2 == 0; };
        partition (A.begin (), A.end (), is_even);
        return A;
    }
};

result

Runtime: 28 ms, faster than 98.35% of C++ online submissions for Sort Array By Parity.

Memory Usage: 9.6 MB, less than 99.36% of C++ online submissions for Sort Array By Parity.