2025-12-01：最小相邻交换至奇偶交替。用go语言，给定一个由互不相同的整数组成的数组 nums。允许的操作是把数组中相邻

福大大架构师每日一题

发布于 2025-12-19 09:27:34

610

2025-12-01：最小相邻交换至奇偶交替。用go语言，给定一个由互不相同的整数组成的数组 nums。允许的操作是把数组中相邻的两个元素互换位置。若一个排列中每一对相邻元素的奇偶性交替出现（即任意相邻的一对中有且只有一个是偶数），则称该排列为“奇偶交错”排列。求将 nums 通过最少次相邻交换变为任意一种奇偶交错排列所需的最小交换次数；若无法通过任何相邻交换得到这样的排列，则返回 -1。

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

nums 中的所有元素都是唯一的。

输入： 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。

题目来自力扣3587。

过程分步说明

1. 识别奇数元素位置
- • 首先，代码遍历输入数组 nums，记录所有奇数元素的原下标位置。这是因为在奇偶交替排列中，奇数的放置位置决定了整体模式。例如，对于数组 [2,4,6,5,7]，奇数元素是 5 和 7，它们的下标分别是 3 和 4。
2. 检查两种交替排列模式的可行性
- • 奇偶交替排列有两种可能模式：
  - • 模式A（起始索引为0）：奇数放置在偶数索引（如索引0、2、4...），偶数放置在奇数索引。
  - • 模式B（起始索引为1）：奇数放置在奇数索引（如索引1、3、5...），偶数放置在偶数索引。
- • 代码会检查每种模式是否可行：模式A需要的奇数个数为 (n+1)//2（向上取整），模式B需要的奇数个数为 n//2（向下取整），其中 n 是数组长度。如果实际奇数个数 m 与模式要求不匹配，则该模式不可行。例如，当 n=5 时，模式A需要3个奇数，模式B需要2个奇数。若实际奇数个数为2，则模式A不可行。
3. 计算每种可行模式的交换次数
- • 对于可行模式，代码计算将每个奇数移动到目标位置所需的“距离和”：
  - • 在模式A下，第 i 个奇数（按顺序）的目标索引是 i*2 + 0。
  - • 在模式B下，第 i 个奇数的目标索引是 i*2 + 1。
- • 对于每个奇数，计算其当前下标 j 与目标下标之差的绝对值 |target_j - j|，并累加所有奇数的绝对值差。这个累加值即为该模式下的最小交换次数。因为相邻交换中，移动一个元素到距离 d 的位置需要 d 次交换，且元素互不相同，使得移动相互独立。例如，将奇数 5（下标3）移动到目标下标2，需要 |2-3|=1 次交换。
4. 确定结果
- • 比较两种模式的交换次数，取最小值作为答案。如果两种模式均不可行（如奇数个数与两种模式要求均不匹配），则返回 -1。在示例 [2,4,6,5,7] 中，模式B可行（奇数个数2等于 5//2=2），计算出的距离和为3，故结果为3。

时间复杂度和空间复杂度

• 总时间复杂度：O(n)，其中 n 是数组长度。过程包括一次数组遍历（收集奇数下标）和两次对奇数列表的遍历（计算两种模式的距离），均为线性操作。
• 总额外空间复杂度：O(n)，主要用于存储奇数下标的列表，最坏情况下（全为奇数）需要 n 个空间。

Go完整代码如下：

import math
from typing import List

def minSwaps(nums: List[int]) -> int:
    pos1 = []  # 车（奇数）的下标
    for i, x in enumerate(nums):
        if x % 2 != 0:
            pos1.append(i)
    
    n = len(nums)
    m = len(pos1)
    
    def calc(start: int) -> int:
        if (n - start + 1) // 2 != m:
            return math.inf
        res = 0
        for i, j in enumerate(pos1):
            res += abs(i * 2 + start - j)
        return res
    
    ans = min(calc(0), calc(1))
    if ans == math.inf:
        return-1
    return ans

def main():
    nums = [2, 4, 6, 5, 7]
    result = minSwaps(nums)
    print(result)

if __name__ == "__main__":
    main()

Python完整代码如下：

# -*-coding:utf-8-*-

import math
from typing import List

def minSwaps(nums: List[int]) -> int:
    pos1 = []  # 车（奇数）的下标
    for i, x in enumerate(nums):
        if x % 2 != 0:
            pos1.append(i)
    
    n = len(nums)
    m = len(pos1)
    
    def calc(start: int) -> int:
        if (n - start + 1) // 2 != m:
            return math.inf
        res = 0
        for i, j in enumerate(pos1):
            res += abs(i * 2 + start - j)
        return res
    
    ans = min(calc(0), calc(1))
    if ans == math.inf:
        return-1
    return ans

def main():
    nums = [2, 4, 6, 5, 7]
    result = minSwaps(nums)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>

using namespace std;

int minSwaps(vector<int>& nums) {
    vector<int> pos1; // 车（奇数）的下标
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] % 2 != 0) {
            pos1.push_back(i);
        }
    }

    int n = nums.size();
    int m = pos1.size();

    auto calc = [&](int start) -> int {
        if ((n - start + 1) / 2 != m) {
            return INT_MAX;
        }
        int res = 0;
        for (int i = 0; i < pos1.size(); i++) {
            res += abs(i * 2 + start - pos1[i]);
        }
        return res;
    };

    int ans = min(calc(0), calc(1));
    if (ans == INT_MAX) {
        return-1;
    }
    return ans;
}

int main() {
    vector<int> nums = {2, 4, 6, 5, 7};
    int result = minSwaps(nums);
    cout << result << endl;
    return0;
}