LeetCode题解 => 922.按奇偶排序数组II（六十八）

按奇偶排序数组II

一、LeetCode题解

瞧一瞧～

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

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

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

二、算法题

题目

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时，i 也是偶数。

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

示例：

输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

提示：

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

解法一（两次扫描）

• 创建新数组用于保存结果，声明一个变量记录下标
• ????第一次扫描偶数，保存在偶数下标位置
• ????第二次扫描基数，保存在奇数下标位置
• 时间复杂度O(N)——遍历了2次数组
• 空间复杂度O(N)——一个新数组

var sortArrayByParityII = function(A) {
    var index = 0
    var res = []
    A.forEach(item => {
        if(item % 2 === 0){
            res[index] = item
            index+=2
        }
    });
    index = 1;// 初始化奇数下标
    A.forEach(item => {
        if(item % 2 !== 0){
            res[index] = item
            index+=2
        }
    });
    return res;
};

解法二（一遍扫描）

• 创建新数组用于保存结果，声明2个变量记录下标
• 扫描一次
• ????下标间隔为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;
};