求最小交换次数

**

求最小交换次数

**
最近遇到了要求最小交换次数的问题，就是给定两个字符串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)
1
2
3
4
5
6