题目描述

主要思想

最少的交换次数等于n减去当前成环的个数
因为当所有的数字按照顺序拍好在自己相应的位置上的时候，每一个数字都是自成环的，会有n个环

只要求解出环的个数就可以得到结果

环的个数的求法

首先题目给定的顺序的成环的方法：位置指向瓶子编号。可能有一个环，也可能有多个环。
选择一个布尔类型的数组，每遍历过一个位置或者一个瓶子编号，就置为true，当一个环内的所有的元素被遍历完成后，退出循环，cnt++

代码

package dbfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 交换瓶子 {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(bufferedReader.readLine());
        int a[]=new int [n+1];
        String p[]=bufferedReader.readLine().split(" ");
        for(int i=1;i<=n;i++){
            a[i]=Integer.parseInt(p[i-1]);
        }
        int cnt=0;
        boolean st[]=new boolean[n+1];
        for(int i=1;i<=n;i++){
            //遍历的是位置
            if(!st[i]){
                //当前的位置没有被遍历过，这句话一定要有
                //因为虽然位置是从前到后遍历的，但是在遍历瓶子的时候位置状态会被更新
                for(int j=i;!st[j];j=a[j]){
                    st[j]=true;

                }
                cnt++;
            }
        }
System.out.println(n-cnt);
    }

}