LeetCode 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
题目描述
题意分析
调整整数数组，使所有奇数位于所有偶数之前，返回调整后的数组。每个元素都要保留，划分依据是元素值的奇偶，不是下标的奇偶，也不要求前后两部分长度相等。
题目不要求同类元素保持原来的相对顺序，因此可以通过交换原地划分。零属于偶数，负数也按自身奇偶处理；题面要求线性时间和常量额外空间。
解法：双指针原地交换
核心思路
[!blue]
用
left、right包围尚未确定归属的区间。始终保证left左边已经全是奇数，right右边已经全是偶数，只有中间部分还需要处理。左指针遇到奇数，可以直接向右跳过，因为它已经位于正确一侧；直到遇到偶数才停下。右指针同理，跳过偶数，直到遇到奇数。如果两指针还没相遇，停下的两个元素恰好都在错误的一侧，一次交换就能同时修复两处位置，再各自向中间推进。
扫描和交换只扩大已经确认的前缀、后缀，不会破坏它们。两指针相遇或交错时，中间至多剩一个元素：它无论是奇数还是偶数，都可以接在对应分区边缘，不会出现偶数位于奇数之前的情况，因此可以结束。
奇偶使用最低位判断，
x & 1为1表示奇数，为0表示偶数，负数也适用。内层扫描同样要检查left < right，避免全奇或全偶时继续越过待处理区间。由于不保证稳定顺序，首尾交换符合本题要求。
解题步骤
- 初始化
left = 0、right = nums.length - 1。- 当
left < right时，让左指针连续跳过奇数，右指针连续跳过偶数；每次读取元素前都检查指针尚未相遇。- 如果扫描后仍有
left < right，交换左侧偶数与右侧奇数，再令left++、right--。- 指针相遇或交错后返回原数组。空数组和单元素数组会直接结束。
代码实现
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)$，只维护边界和交换所需的常量变量，原地完成分区。
关键点总结
[!green]
- 左侧已确认全奇，右侧已确认全偶，所有操作都围绕未确定的中间区间进行。
- 两端分别寻找错位元素，一次交换同时修复两个位置。
- 题目不要求稳定顺序，是可以直接首尾交换的前提。
易错点总结
[!yellow]
- 内层扫描漏掉边界判断，全奇或全偶数组可能一直推进到越界位置。
- 外层使用
left <= right，而内部操作仅在严格小于时推进，会在两指针相遇后无法结束。- 将奇数判断写成
x % 2 == 1，在 Java、Go 中会错判负奇数；可使用最低位或判断余数不等于零。- 内层扫描后不重新判断
left < right就交换，可能干扰已经确认的分区。- 若要求同类元素保持原顺序，这段首尾交换代码不满足稳定性，不能把两种题型的要求混为一谈。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 905. 按奇偶排序数组 | 简单 | 划分方法相同，但原题偶数在前，本题奇数在前，判定方向相反。 |
| 补充题 174. 数组的稳定奇偶划分 | 中等 | 变形题要求同类元素保持原顺序，本题没有稳定性要求，可使用两端交换。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！