**

求最小交换次数

**
最近遇到了要求最小交换次数的问题，就是给定两个字符串for example :
str=“43216587”;
求从str到顺序最少要交换几步。
翻了很久网上的解答，由于水平限制不会一些算法，很久没有找到能懂的解法，然后就看到了一篇博客给出的一种特别的解法。
**
1):先复制字符串到str1，用sort排序

**
2):假如现在遍历str，如果在相同位置且两个字符串中那个位置数字相同的话去掉（这里用visited模拟去掉数字）

**
3):然后统计在str中剩下的数字能形成几个环，比如现在我们给一个k= str[ 1 ] = ‘4’ , k=4 , 用 j 记录下坐标 j = i = 1，圈数加一，然后进入循环判断k是否等于b[ j ]，若相等则break，若不等则j = str[j]，然后就得到了一个圈，而遍历过的所有数都用visited标记，保证不再判断那些位置。

**
4）：得到圈数之后我们统计相同位置上数字不同的个数，再减去圈数就得到了最小交换次数。

**
下面解释原理，假设我们有字符串“2，1”，成一个圈，圈中有两个元素，我们交换一次，假如字符串”3 , 1 ,2 “成一3元素的环我们交换2次，注意“3， 2 ，1”实际上是2元素环，以此类推，n元素环就交换n-1次，故我们统计所有相同位置不相同数字位置的个数anum，目的是利用环数num与anum的差表示要交换的次数。

附上代码

#include<bits/stdc++.h> //#include<queue> using namespace std; int main() {  ios::sync_with_stdio(false); long long b[100010];int visited[100010]={0}; long long a[100010]; int t;  cin >> t; for(int i=1;i<=t;i++) {   cin >> a[i];   b[i]=a[i] ; //copy原数组  } sort(a+1,a+t+1); //数组从1开始  int num=0; //环数 for(int i=1;i<=t;i++) { int k=0;int j=0; //k用来标记环的顶点值，等待下一个值回到k if(a[i]!=b[i] && visited[i]==0) {    k=b[i];      j=i;     num++;    visited[i]=1; //标记遍历过的位置 while(1) {     visited[j]=1; //这部分写不大好，意思就是遍历一个环     j=b[j]; if(k==b[j]) {      visited[j]=1; break; } } } else{    visited[i]=1; } } int anum=0; for(int i=1;i<=t;i++) { int k=0;int j=0;int l; if(a[i]!=b[i]) {    k=b[i];    j=i;    anum++; } }  cout << anum-num; } 

感谢那个博主的启发，可惜找不到连接了，等找到了原博客再补上。