LCR 139.训练计划 I

难度：🟢 简单

标签：数组、双指针、排序

链接：LCR 139. 训练计划 I (剑指 Offer 21. 调整数组顺序使奇数位于偶数前面)

题目描述

给定一个整数数组 actions，请实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

示例 1：

输入：actions = [1, 2, 3, 4]
输出：[1, 3, 2, 4] 
注：[3, 1, 2, 4] 也是正确的答案之一。

解题思路

核心思想

本题的核心是在原地对数组进行分区操作，将数组分为“奇数区”和“偶数区”两部分，而不需要关心奇数或偶数内部的相对顺序。

思路选择

快慢指针法 是解决此问题的最优思路。

• 我们使用一个“慢指针” (slow)，它代表“奇数区”的边界，即下一个奇数应该被放置的位置。

• 我们使用一个“快指针” (fast)，它用于遍历整个数组，寻找奇数。

• 当快指针 fast 遇到一个奇数时，就将这个奇数与慢指针 slow 指向的位置进行交换。交换完成后，将慢指针 slow 向前移动一位，扩大“奇数区”的范围。

关键步骤

1. 初始化指针：初始化慢指针 slow = 0，快指针 fast = 0。

2. 循环遍历：用快指针 fast 遍历整个数组，从头到尾。

3. 寻找奇数： a. 如果 actions[fast] 是一个奇数，则它应该被放到“奇数区”。 b. 我们将 actions[fast] 与 actions[slow] 进行交换。 c. 交换后，slow 指针加一，表示“奇数区”扩大了一位。

4. 返回结果：遍历结束后，所有奇数都被交换到了数组的前半部分，返回修改后的数组 actions 即可。

代码实现

/**
 * @param {number[]} actions
 * @return {number[]}
 */
var trainingPlan = function (actions) {
    // slow 指针指向下一个奇数应该被放置的位置 (奇数区的边界)
    let slow = 0;

    // fast 指针用于遍历整个数组寻找奇数
    for (let fast = 0; fast < actions.length; fast++) {
        // 如果快指针找到了一个奇数
        if (actions[fast] % 2 === 1) {
            // 将该奇数与慢指针所在位置的元素交换
            // 这样就将奇数移到了奇数区
            [actions[slow], actions[fast]] = [actions[fast], actions[slow]];
            // 慢指针前进，扩大奇数区的范围
            slow++;
        }
    }

    return actions;
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是数组 actions 的长度。快慢指针都只对数组进行一次完整的遍历。

• 空间复杂度：O(1) 我们是在原数组上进行操作，只使用了常数个额外变量作为指针，空间消耗是恒定的。

相关题目

• 0283.移动零

• 0075.颜色分类

• 0027.移除元素

总结

本题是双指针思想在数组原地分区问题中的一个经典应用。通过“慢指针定义边界，快指针负责探索和交换”的模式，可以非常高效地完成原地排序或分区任务。这种解法不仅代码简洁，而且时空效率都非常高。