这是一道细读题目就能做出来的真题~

题目来源:交换瓶子

• 感谢优秀博客：AcWing 1224. 交换瓶子

题目描述
交换瓶子
有N个瓶子，编号 1 ~ N，放在架子上。
比如有5个瓶子：
2 1 3 5 4
要求每次拿起2个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换2次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
输入格式为两行：
第一行: 一个正整数N（N<10000）, 表示瓶子的数目
第二行：N个正整数，用空格分开，表示瓶子目前的排列情况。
输出数据为一行一个正整数，表示至少交换多少次，才能完成排序。
例如，输入：
5
3 1 2 5 4
程序应该输出：
3
再例如，输入：
5
5 4 3 2 1
程序应该输出：
2

题目分析

1. 特别要注意的是乱序的数均为1~n的排列，也就是要使1~n的排列有序
   如：3 1 2 5 4
   最终结果：1 2 3 4 5

O(n^2)的常规解法

算法思想

1. 很容易想到遍历数组 a[]的同时，如果 a[i]!=i,就去找a[j]==a[i]，然后change(a[i],a[j])
2. 每次出现a[i]!=i，便记一次ans++，最后得到ans即‘最少交换次数’

• 该算法时间复杂度O(N^2)

—————————————·AC·900ms——————————————

#include <iostream>

using namespace std;

int n, ans = 0; 
int a[10005];
int index(int x){
	for(int i = 1; i <= n; ++i){
		if(a[i] == x)
			return i;
	}
	return -1;
}
void change(int i, int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i){
		if(a[i] != i){
			ans++;
			change(i, index(i));
		}
	}
	printf("%d\n", ans);
	return 0;
}

O(n)的绝妙解法

如 3 1 2 5 4
最终结果 1 2 3 4 5
“错位”的元素可构成如下2个集合
[1 2 3]、[4 5]
a[1]=3,a[2]=1,a[3]=2; a[4]=5,a[5]=4;

算法思想

1. 遍历a[]的时候，便可以借助下标，通过一个元素扫描到整个集合
   如 3 1 2 4 5
   通过a[1]=3可先后扫描到a[3],a[2];
   通过a[4]=5可扫描到a[5]
2. 扫描的次数ans即“错位”集合的个数，那么‘最少交换次数’即n-ans

• 因为每个元素仅扫描一次，盲猜该算法时间复杂度O(N)

——————————————·AC·25ms——————————————

//精妙的算法往往简洁
#include <iostream>
#include <algorithm>
using namespace std;

int n, ans = 0; 
int a[10005];
int st[10005];
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i){
		if(!st[i]){
			ans++;
			for(int j = i; !st[j]; j=a[j]){
				st[j] = 1;
			}
		}
	}
	printf("%d\n", n-ans);
	return 0;
}