给你一个由互不相同的整数组成的数组 nums。 在一次操作中，你可以交换任意两个相邻元素。 在一...

思路解析

1. 合法性判断

   • 设 evenCnt、oddCnt 为偶数/奇数个数。
   • 交替排列时，两类个数之差不能超过 1；否则必定无法重排，直接返回 -1。

2. 记录原始下标

   • 扫描一次 nums，把偶数出现的下标存到 evenPos，奇数出现的下标存到 oddPos。
   • 两个列表本身保持了元素在原数组中的先后顺序，这一点很关键。

3. 枚举起始奇偶性

   • 如果 evenCnt == oddCnt，既可以 “偶-奇-偶-奇…” 也可以 “奇-偶-奇-偶…”，两种都要算，取较小者。
   • 如果 evenCnt > oddCnt（只可能多 1 个），排列必须从偶数开头；反之亦然。

4. 计算最少相邻交换次数

   • 对于某一种起始模式，只需要把数量较多或规定在偶数位(0,2,4…)的那一类按当前顺序放到目标坐标即可。
   • 令 target[i] = 2*i 为第 i 个该类元素理应出现的位置，下标差的绝对值就是它要走的步数；相邻交换一次只能把元素移动 1 位，所以 $$cost = \sum_{i} |\,pos[i] - 2i\,|$$
   • 不必同时对两类元素求和——把偶数放到正确槽位后，奇数自然落到剩余位置，步数不会被遗漏也不会被重复统计。

5. 复杂度

   • 只需一次遍历 + 最多两次对列表求和，时间 O(n)、空间 O(n)。
   • 对 n ≤ 10^5，步数上界约 $1.25\times10^9$，用 long 保存再强转 int 安全无误。

代码（Java 17）

java
class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        List<Integer> evenPos = new ArrayList<>();
        List<Integer> oddPos  = new ArrayList<>();

        for (int i = 0; i < n; ++i) {
            if ((nums[i] & 1) == 0) {
                evenPos.add(i);
            } else {
                oddPos.add(i);
            }
        }

        int evenCnt = evenPos.size(), oddCnt = oddPos.size();
        if (Math.abs(evenCnt - oddCnt) > 1) return -1;   // 无解

        long ans = Long.MAX_VALUE;

        // 情况 A: 以偶数开头 (偶数占 0,2,4,...)
        if (evenCnt >= oddCnt) {
            long cost = 0;
            for (int i = 0; i < evenPos.size(); ++i) {
                cost += Math.abs(evenPos.get(i) - (long)(2 * i));
            }
            ans = Math.min(ans, cost);
        }

        // 情况 B: 以奇数开头 (奇数占 0,2,4,...)
        if (oddCnt >= evenCnt) {
            long cost = 0;
            for (int i = 0; i < oddPos.size(); ++i) {
                cost += Math.abs(oddPos.get(i) - (long)(2 * i));
            }
            ans = Math.min(ans, cost);
        }

        return (int) ans;   // 上限 1.25e9，fits in int
    }
}

例子核对

全部符合题意且 O(n) 通过大数据不会超时。