小红的有序数组

[题目链接](https://www.nowcoder.com/practice/d4ee2b59f3564cfcac9a66161bca5a5c)

思路

给定一个长度为 $n$ 的排列，每次操作可以选择位置奇偶性相同的两个位置并交换它们的值，求将数组排成升序所需的最少操作次数，若无法完成输出 $-1$ 。

判断可行性

位置 $i$ （1-indexed）上的元素值 $a_i$ ，排好序后应该在位置 $a_i$ 。由于只能在同奇偶位置之间交换，元素只能在奇数位置之间移动、或在偶数位置之间移动。因此， $i$ 和 $a_i$ 的奇偶性必须相同，否则无解，输出 $-1$ 。

计算最少交换次数

判断可行后，问题转化为：给定一个排列，求将其排成有序所需的最小交换次数。

这是一个经典结论：对排列做循环分解，长度为 $k$ 的环需要 $k - 1$ 次交换。总交换次数 = $\sum (k_i - 1)$ = $n - \text{环的个数}$ 。

注意，虽然奇数位置和偶数位置各自独立，但由于整体仍然构成一个排列（可行性已保证每个元素都能到达目标位置），直接对整个排列做循环分解即可——奇数位置上的环和偶数位置上的环自然不会交叉。

样例演示

数组 $[1, 4, 5, 2, 3]$ ：

检查奇偶性：位置 1 值 1（同奇），位置 2 值 4（同偶），位置 3 值 5（同奇），位置 4 值 2（同偶），位置 5 值 3（同奇）。全部合法。
循环分解： $1 \to 1$ （自环）， $2 \to 4 \to 2$ （长度 2）， $3 \to 5 \to 3$ （长度 2）。
交换次数： $0 + 1 + 1 = 2$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    // 检查奇偶性
    for(int i=1;i<=n;i++){
        if((i%2)!=(a[i]%2)){
            printf("-1\n");
            return 0;
        }
    }
    // 循环分解求最少交换次数
    vector<bool> vis(n+1,false);
    int ans=0;
    for(int i=1;i<=n;i++){
        if(vis[i]||a[i]==i) continue;
        int cnt=0, j=i;
        while(!vis[j]){
            vis[j]=true;
            j=a[j];
            cnt++;
        }
        ans+=cnt-1;
    }
    printf("%d\n",ans);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) a[i] = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            if ((i % 2) != (a[i] % 2)) {
                System.out.println(-1);
                return;
            }
        }
        boolean[] vis = new boolean[n + 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (vis[i] || a[i] == i) continue;
            int cnt = 0, j = i;
            while (!vis[j]) {
                vis[j] = true;
                j = a[j];
                cnt++;
            }
            ans += cnt - 1;
        }
        System.out.println(ans);
    }
}

import sys
input = sys.stdin.readline

n = int(input())
a = [0] + list(map(int, input().split()))

for i in range(1, n + 1):
    if i % 2 != a[i] % 2:
        print(-1)
        exit()

vis = [False] * (n + 1)
ans = 0
for i in range(1, n + 1):
    if vis[i] or a[i] == i:
        continue
    cnt = 0
    j = i
    while not vis[j]:
        vis[j] = True
        j = a[j]
        cnt += 1
    ans += cnt - 1

print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = [0, ...lines[1].split(' ').map(Number)];
    for (let i = 1; i <= n; i++) {
        if (i % 2 !== a[i] % 2) {
            console.log(-1);
            return;
        }
    }
    const vis = new Array(n + 1).fill(false);
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        if (vis[i] || a[i] === i) continue;
        let cnt = 0, j = i;
        while (!vis[j]) {
            vis[j] = true;
            j = a[j];
            cnt++;
        }
        ans += cnt - 1;
    }
    console.log(ans);
});

复杂度分析

时间复杂度： $O(n)$ 。奇偶性检查和循环分解各遍历一次数组。
空间复杂度： $O(n)$ 。存储数组和访问标记。