LeetCode题解 => 905.按奇偶排序数组（六十七）

按奇偶排序数组

一、LeetCode题解

瞧一瞧～

• 博健的LeetCode题解：Gitbook版本传送门
• 博健的LeetCode题解：CSDN传送门
• 有趣的CSS：Gitbook传送门
• 前端进阶笔记：Gitbook传送门

做题路线（ ** =当前阶段）

• 阶段一（解题总数，单题题解数至上）**
• 阶段二（解题质量至上）
• 阶段三（算法思想至上）

二、算法题

题目

给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。

????你可以返回满足此条件的任何数组作为答案。

示例：

输入：[3,1,2,4]
输出：[2,4,3,1]
输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。

提示：

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

解法一（两次扫描）

• 创建新数组用于保存结果
• ????第一次扫描偶数
• ????第二次扫描基数
• 时间复杂度O(N)——遍历了2次数组
• 空间复杂度O(N)——一个新数组

var sortArrayByParity = function(A) {
    var res = []
    A.forEach(item => {
        if(item % 2 === 0){
            res.push(item)
        }
    });
    A.forEach(item => {
        if(item % 2 !== 0){
            res.push(item)
        }
    });
    return res;
};

解法二（一遍扫描）

• 创建新数组用于保存结果，声明2个变量记录下标
• 扫描一次

var sortArrayByParity = function(A) {
    var left = 0,right = A.length-1;
    var res = []
    A.forEach(item => {
        if(item % 2 === 0){
            res[left++] = item
        }else{
            res[right--] = item
        }
    });
    return res;
};