LeetCode 题解工作台
最小相邻交换至奇偶交替
给你一个由互不相同的整数组成的数组 nums 。 在一次操作中，你可以交换任意两个 相邻 元素。 在一个排列中，当所有相邻元素的奇偶性交替出现，我们认为该排列是 有效排列 。这意味着每对相邻元素中一个是偶数，一个是奇数。 请返回将 nums 变成任意一种 有效排列 所需的最小相邻交换次数。 如果无法…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
对于一个有效排列，奇数和偶数的个数只能相差 1 或者相等。因此，如果奇数和偶数的个数相差超过 1，则无法构成有效排列，直接返回 -1。 我们用一个数组 来存储奇数和偶数的下标，其中 存储偶数的下标，而 存储奇数的下标。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个由互不相同的整数组成的数组 nums 。
在一次操作中，你可以交换任意两个 相邻 元素。
在一个排列中，当所有相邻元素的奇偶性交替出现，我们认为该排列是 有效排列。这意味着每对相邻元素中一个是偶数，一个是奇数。
请返回将 nums 变成任意一种 有效排列 所需的最小相邻交换次数。
如果无法重排 nums 来获得有效排列，则返回 -1。
示例 1：
输入： nums = [2,4,6,5,7]
输出：3
解释：
将 5 和 6 交换，数组变成 [2,4,5,6,7]
将 5 和 4 交换，数组变成 [2,5,4,6,7]
将 6 和 7 交换，数组变成 [2,5,4,7,6]。此时是一个有效排列。因此答案是 3。
示例 2：
输入： nums = [2,4,5,7]
输出： 1
解释：
将 4 和 5 交换，数组变成 [2,5,4,7]。此时是一个有效排列。因此答案是 1。
示例 3：
输入： nums = [1,2,3]
输出： 0
解释：
数组已经是有效排列，因此不需要任何操作。
示例 4：
输入： nums = [4,5,6,8]
输出：-1
解释：
没有任何一种排列可以满足奇偶交替的要求，因此返回 -1。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109nums中的所有元素都是 唯一 的
解题思路
方法一：分类讨论 + 贪心
对于一个有效排列，奇数和偶数的个数只能相差 1 或者相等。因此，如果奇数和偶数的个数相差超过 1，则无法构成有效排列，直接返回 -1。
我们用一个数组 来存储奇数和偶数的下标，其中 存储偶数的下标，而 存储奇数的下标。
如果奇数和偶数的个数相等，则可以有两种有效排列：奇数在偶数前面，或者偶数在奇数前面。我们可以计算这两种排列的交换次数，取最小值。
如果奇数的个数大于偶数的个数，则只有一种有效排列，即奇数在偶数前面。此时，我们只需要计算这种排列的交换次数。
因此，我们定义一个函数 ，其中 表示第一个元素的奇偶性（0 表示偶数，1 表示奇数）。该函数计算从当前排列到以 开头的有效排列所需的交换次数。我们只需要遍历 中的下标，计算每个下标与其在有效排列中的位置之间的差值之和。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def minSwaps(self, nums: List[int]) -> int:
def calc(k: int) -> int:
return sum(abs(i - j) for i, j in zip(range(0, len(nums), 2), pos[k]))
pos = [[], []]
for i, x in enumerate(nums):
pos[x & 1].append(i)
if abs(len(pos[0]) - len(pos[1])) > 1:
return -1
if len(pos[0]) > len(pos[1]):
return calc(0)
if len(pos[0]) < len(pos[1]):
return calc(1)
return min(calc(0), calc(1))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) to count parity and compute swaps since each element is visited once for position correction. Space complexity is O(1) extra if counting in place or O(n) if storing positions separately. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check parity counts first; mismatched counts indicate impossible arrangement.
- question_mark
Consider greedy placement: always move the nearest correct parity element to the current position.
- question_mark
Evaluate both starting options when counts are equal to ensure minimal swaps.
常见陷阱
外企场景- error
Ignoring the case where abs(evenCnt - oddCnt) > 1 and attempting swaps unnecessarily.
- error
Counting swaps incorrectly by assuming all elements can move freely instead of adjacent swaps only.
- error
Not checking both starting parity options when counts are equal, leading to suboptimal swap count.
进阶变体
外企场景- arrow_right_alt
Allow swaps between any two elements, not just adjacent ones, which changes the minimal swap calculation.
- arrow_right_alt
Require the array to alternate parity but allow repeated numbers, which changes the invariant check.
- arrow_right_alt
Count swaps to alternate parity for multiple arrays in a batch, needing efficient cumulative computation.