题目描述

有 N 个瓶子，编号 1∼N，放在架子上。

比如有 5 个瓶子：

2 1 3 5 4

要求每次拿起 2 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 2 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式
第一行包含一个整数 N，表示瓶子数量。
第二行包含 N 个整数，表示瓶子目前的排列状况。
输出格式
输出一个正整数，表示至少交换多少次，才能完成排序。
数据范围
1≤N≤10000

样例1:

5
3 1 2 5 4

样例2:

5
5 4 3 2 1

输出样例1：

3

输出样例2：

2

3 1 2 5 4，这一出数据，3要到2那里，2要到1那里，1要到3那里，刚好形成一个闭环，交换的次数恰好为这个圆环的边数
减掉1。找出这个环之后在这个环上的数字恰好能回到他们本来的位置。那么我们就可以确定目标就是找出有几个环，并计算出他们的边，然后进行统计。那么如何从环中出来呢？那么就找一个数组记录一下那个点是否被遍历过。被遍历过的点的值给改掉，还能当循环条件.

置换群法

逆十字的题解

时间复杂度：最好的情况就是O(n)，最坏的情况就是O(n^2)

Java 代码

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n + 1];
        boolean[] sr = new boolean[n + 1];
        int min = 0;
        for(int i = 1;i <= n;i++) {
            a[i] = in.nextInt();
            sr[i] = true;
        }
        for(int i = 1;i <= n;i++){
            if(a[i] == i || !sr[i]) continue;//相等那么就不需要交换
            int m = 0;
            int l = a[i];
            while(sr[l]) {
                sr[l] = false;
                l = a[l];
                m++;
            }
            min += m - 1;
        }
        System.out.println(min);
    }
}