LeetCode 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
目录
题目描述
题意分析
要的是一次按奇偶的二分区：调整完之后，数组前半段全是奇数、后半段全是偶数，返回调整后的数组即可。
需要格外留意题目没有要求什么：它不要求奇数之间保持原有相对顺序，也不要求偶数之间保持原有相对顺序，任何一种满足前奇后偶的排列都会被判定为正确。少了「稳定」这个约束，就意味着元素可以被随意搬动，而不必像插入排序那样整段平移。
约束信号是数组长度可达 50000、元素值在 1 到 10000 之间。长度五万说明需要线性做法，$O(n^2)$ 的逐个前移会被卡；元素全为正数说明用取模判奇偶不必担心负数在某些语言里取模得到
-1的问题；同时题面只给了一个数组、没给额外空间限制，但既然是「调整顺序」，面试官通常期待原地完成。边界上要考虑：数组只有一个元素时无需任何调整；全是奇数或全是偶数时不应发生任何交换；奇偶恰好完全交错时交换次数最多；空数组或长度为 1 时循环体一次都不该进入。
解法：双指针原地交换
核心思路
题目只要求奇数在偶数前面，不要求保持相对顺序，因此可以原地交换。用
left从左找偶数、right从右找奇数；找到一对错位元素后交换，一次修正两个位置。循环不变量：每轮开始时，
[0, left)全是奇数，(right, n - 1]全是偶数。左指针跳过奇数、右指针跳过偶数，都只会扩大已经正确的区间；交换后，新放到left的是奇数，新放到right的是偶数，所以不变量继续成立。两个指针相遇或交错时，中间未分类区间为空或只剩一个元素。结合不变量，数组必然已经形成「前奇后偶」的分区，因此算法正确。
若题目额外要求稳定性，首尾交换会打乱同类元素的相对顺序，此时应改用额外数组稳定收集；本题没有这个限制。
解题步骤
- 初始化
left = 0、right = nums.length - 1。- 在
left < right的前提下，右移left，跳过已经在左侧的奇数。- 左移
right，跳过已经在右侧的偶数。- 若两指针尚未相遇，交换两处错位元素，并让两指针各向中间移动一步。
- 指针相遇后返回原数组。
例如
[1, 2, 3, 4]：左侧停在2，右侧停在3，交换后得到[1, 3, 2, 4]。全奇、全偶或单元素数组只会移动指针，不会发生无效交换。
代码实现
class Solution {
public int[] exchange(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
while (left < right && (nums[left] & 1) == 1) {
left++;
}
while (left < right && (nums[right] & 1) == 0) {
right--;
}
if (left < right) {
int value = nums[left];
nums[left] = nums[right];
nums[right] = value;
left++;
right--;
}
}
return nums;
}
}
func exchange(nums []int) []int {
left := 0
right := len(nums) - 1
for left < right {
for left < right && nums[left]&1 == 1 {
left++
}
for left < right && nums[right]&1 == 0 {
right--
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
return nums
}
复杂度分析
- 时间复杂度：$O(n)$。两个指针都只向中间移动，每个元素最多被检查一次。
- 空间复杂度：$O(1)$。只使用指针和一个交换变量，原地完成分区。
关键点总结
- 不要求稳定性，才可以使用首尾交换；若要求稳定，应换解法。
- 不变量是「左侧已确认全奇、右侧已确认全偶」，搜索和交换都围绕它展开。
- 两个内层循环都要带
left < right，避免全奇或全偶时越界。- 用最低位
(x & 1)判断奇偶，也能正确处理允许负数的变体。
易错点总结
- 漏写边界守卫：
[1, 3, 5]中左指针会一直前进；内层循环必须同时判断left < right。- 外层使用
left <= right：单元素数组可能无法推进而死循环，条件应为left < right。- 要求稳定却仍首尾交换：同类元素的相对顺序可能被改变，先确认题目是否要求稳定。
- 负数变体用
x % 2 == 1：Java、Go 中-3 % 2 == -1，会误判；使用(x & 1) == 1或x % 2 != 0。- 搜索写成
if且交换后不推进：指针可能反复交换同一对元素；搜索应使用while，交换后直接收缩边界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 27. 移除元素 | 简单 | 同向快慢指针原地覆盖，还要额外返回保留元素的个数 |
| 75. 颜色分类 | 中等 | 三分区而非二分区，需要三个指针且中间指针在换后不能盲目前进 |
| 283. 移动零 | 简单 | 要求非零元素保持相对顺序，只能同向覆盖而不能首尾对调 |
| 905. 按奇偶排序数组 | 简单 | 同为奇偶二分区，但要求偶数在前，判定方向相反 |
| 922. 按奇偶排序数组 II | 简单 | 要求奇偶交替落位，双指针分别只在奇数位和偶数位上跳 |
| 328. 奇偶链表 | 中等 | 载体换成链表且按结点位置分组，靠拆分再拼接而非交换值 |