数据结构与算法之排序: Leetcode 922. 按奇偶排序数组 II (Typescript版)

按奇偶排序数组 II

• https://leetcode.cn/problems/sort-array-by-parity-ii/

描述

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

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

• 你可以返回 任何满足上述条件的数组作为答案 。

示例 1

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

示例 2

输入：nums = [2,3]
输出：[2,3]
1
2

提示

• 2 <= nums.length <= 2 * $10^4$
• nums.length 是偶数
• nums 中一半是偶数
• 0 <= nums[i] <= 1000

进阶

• 可以不使用额外空间解决问题吗？

算法实现

1 ）原生sort + 一般方法

function sortArrayByParityII(nums: number[]): number[] {
    // 进行升序排序
    nums.sort((a, b) => a - b);
    // 声明一个空数组用来存储奇偶排序后的数组
    const res: number[] = [];
    // 记录奇数、偶数位下标
    let odd: number = 1;
    let even: number = 0;
    // 对数组进行遍历
    nums.forEach(item => {
        if (item % 2 === 1) {
            res[odd] = item;
            odd += 2;
        } else {
            res[even] = item;
            even += 2;
        }
    })
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 基于题目，我们需要知道，一半整数是奇数，另一半整数是偶数，可知，整个数组长度是偶数(数学基础)
• 先整体排好序了，再基于原数组分别处理位置的问题，这里多使用了 res 的空间

2 ）两次遍历 + & 运算判断奇偶对位存放

function sortArrayByParityII(nums: number[]): number[] {
    const ans: number[] = new Array(nums.length);
    let i: number = 0; // 默认i以0开始
    for (const x of nums) {
        if (!(x & 1)) {
            ans[i] = x;
            i += 2;
        }
    }
    i = 1; // 这里 i 从1开始
    for (const x of nums) {
        if (x & 1) {
            ans[i] = x;
            i += 2;
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 这是官方提供方案，题目没有要求数组完全有序
• 注意，“&”的运算方法：
  • 两个数值的个位分别相与，同时为1才得1，只要一个为0就为0。
  • 可以利用 & 的运算特性，来判断一个数是否为偶数。
  • 需要注意条件是 非负整数
• 但是，这里仍然开辟了 新的 ans 数组空间

3 ）双指针，奇偶交换

function sortArrayByParityII(nums: number[]): number[] {
    const n: number = nums.length;
    let j: number = 1; // j奇数从1开始
    // i 索引从0开始，偶数，每次递增2，仍为偶数
    for (let i: number = 0; i < n; i += 2) {
        // i是偶数, 如果当前 nums[i] 是奇数, 注意，题目要求 nums[i] 最终也是偶数
        if (nums[i] & 1) {
            // 如果 nums[j]是奇数, j递增2，j仍旧奇数
            while (nums[j] & 1) {
                j += 2;
            }
            // 跳出while时, nums[j]为偶数了，交换 nums[i](当前奇数, 应为偶数) 和 nums[j](当前偶数, 应为奇数)
            [nums[i], nums[j]] = [nums[j], nums[i]];
        }
    }   
    return nums;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 这也是官方提供的一个解法，符合题意要求
• 题目没有要求数组完全有序
• 做题的步骤和思路都写在上面注释上了