面试题：给定一个无序数列，通过交换任意两个元素给数列重新排序。求最少需要多少次交换，能把数组排成按1-n递增的顺序，（数组中的元素互不重复）超简单理解方法

如果 v = { 1,3,4,2,5};;找最少交换次数 就是在origin和destin中由3(origin)》2(destin) ---- 2(origin)》4(destin) --4(origin)==》2(destin) 形成闭环就可以了 然后将环中元素个数-1 就是最小交换次数，，当然我们需要用此方法 找每一个环中元素个数 然后将每个环中的最少交换次数累加起来就可以了。其中flag 的作用是为了标志我们是否访问过此位置 。

不多说，直接看代码

#include<iostream> #include<vector> #include<unordered_map> #include<algorithm> using namespace std; /** * 就是在origin和destin中来回的找映射关系 找到环的长度 */ int getMinSwaps(vector<int> v) { vector<int> v1(v); //将v内元素复制到v1。 sort(v1.begin(), v1.end()); unordered_map<int, int> m; int len = v.size(); for (int i = 0; i < len; i++) { m[v1[i]] = i; // 建立每个元素与dest位置的映射关系 } unordered_map<int, int> n; for (int i = 0; i < len; i++) { n[v[i]] = i; // 建立每个元素与origin位置的映射关系（方便我们后买呢代码中的由3(origin)==》2(destin) --n中映射关系做桥梁-- 2(origin)==》4(destin) --n中映射关系做桥梁-- 4(origin)==》3(destin)） } int ret = 0; vector<bool> flag(len, false); //初始化 for (int i = 0; i < len; i++) { if (!flag[i]) { int j = i; int swapcount = 0; while (!flag[j]) { flag[j] = true; if (j!= m[v[j]]) { j = n[v1[j]]; } swapcount++;//记录形成环中的元素个数 } swapcount--; //最小交换次数=环中的元素个数-1 ret += swapcount;//记录交换次数 } } cout << "ret=" << ret << endl; return ret; } vector<int> v; int main() { //v = { 2,6,3,5,4,9,7,8,10 }; v = { 1,3,4,2,5,9,7,8,10 }; int num = getMinSwaps(v); cout << "交换次数：" << num << endl; return 0; }

当然还有种方法，就是每次j= m[v[j]] 就可以了，如下，具体理解我就不多说了，自己画一遍就知道了！！！

#include<iostream> #include<vector> #include<unordered_map> #include<algorithm> using namespace std; /** */ int getMinSwaps(vector<int> v) { vector<int> v1(v); //将v内元素复制到v1。 sort(v1.begin(), v1.end()); unordered_map<int, int> m; int len = v.size(); int ret = 0; for (int i = 0; i < len; i++) { m[v1[i]] = i; // 建立每个元素与其应放位置的映射关系 } vector<bool> flag(len, false); //初始化 for (int i = 0; i < len; i++) { if (!flag[i]) { int j = i; int swapcount = 0; // 环的中数的交换次1数=环的大小-1 while (!flag[j]) //对环处理 { flag[j] = true; j = m[v[j]]; //原序列中j位置的元素在有序序列中的位置 swapcount++; } swapcount--; //最小交换次数=环中的元素个数-1 ret += swapcount;//记录交换次数 } } return ret; } vector<int> v; int main() { //v = { 2,6,3,5,4,9,7,8,10 }; v = { 1,3,4,2,5,9,7,8,10 }; int num = getMinSwaps(v); cout << "交换次数：" << num << endl; return 0; }