LeetCode 补充题 174. 数组的稳定奇偶划分
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ LCR 139. 训练计划 I
LeetCode 原题只要求奇数位于偶数之前；本文额外要求分别保持两类元素的原始相对顺序。
:::
给定整数数组
nums，将全部奇数放在偶数之前，并分别保持奇数内部、偶数内部的原始相对顺序。返回调整后的数组。这里采用辅助数组的线性时间版本。
示例 1：
输入：
nums = [2,1,4,3,6,5]
输出：[1,3,5,2,4,6]
解释： 奇数仍按 1、3、5 排列，偶数仍按 2、4、6 排列。
示例 2：
输入：
nums = [2,4,6]
输出：[2,4,6]
解释： 没有奇数，原有顺序不变。
提示：
0 <= n <= 5000- 数组中每个数的值
0 <= val <= 10000
题意分析
条件不仅是奇数在前，还要求两组内部维持原顺序。首尾交换可能打乱这种稳定性；题目允许辅助数组，按顺序分别收集两组就是直接的线性方案。
解法：两次稳定扫描写入辅助数组
核心思路
[!blue]
第一遍从左到右扫描，只将奇数依次写入结果。第二遍仍按相同方向扫描，只追加偶数。这样所有奇数位于偶数之前，而每组中的任意两个元素仍按原下标先后输出。
每个整数恰好属于奇数或偶数中的一组，因此恰好输出一次，不会遗漏或重复。用最低位判断奇偶，不依赖数组下标，也无需改变输入顺序。
结果预留
n个位置，写入总数恰好为n。空数组返回空结果，全部同奇偶时保持原数组顺序；两次扫描仍为线性时间，存储结果需要线性空间。
解题步骤
- 分配与输入等长的结果数组。
- 从左向右写入所有奇数，再从左向右写入所有偶数。
- 返回结果，原输入数组保持不变。
代码实现
class Solution {
public int[] reorder(int[] nums) {
int[] result = new int[nums.length];
int write = 0;
for (int x : nums) {
if ((x & 1) != 0) {
result[write++] = x;
}
}
for (int x : nums) {
if ((x & 1) == 0) {
result[write++] = x;
}
}
return result;
}
}
func reorder(nums []int) []int {
result := make([]int, 0, len(nums))
for _, x := range nums {
if x&1 != 0 {
result = append(result, x)
}
}
for _, x := range nums {
if x&1 == 0 {
result = append(result, x)
}
}
return result
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
每一组都按输入顺序写入，因此稳定性直接由扫描方向保证；辅助空间是明确的代价；首尾交换的原地分区不能保证稳定。
易错点总结
[!yellow]
奇偶按数值判断，不是按下标；不能用 x%2==1 排除负奇数；不要把本解写成 $O(1)$ 空间。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 | 简单 | 本题增加组内稳定性要求，原地两端交换的基础解不能直接保留相对顺序。 |
| 86. 分隔链表 | 中等 | 同样按条件稳定分成两组；链表可用两条结果链接回，数组版本用辅助空间保存顺序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！