Given any permutation of the numbers {0, 1, 2,..., N?1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:
Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.
Each input file contains one test case, which gives a positive N (≤ 105) followed by a permutation sequence of {0, 1, ..., N?1}. All the numbers in a line are separated by a space.
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
10
3 5 7 2 6 4 9 0 8 1
9
题目就是要求我们用‘0‘这个元素去对数组中的元素进行交换，最后使得每个元素的值都与该元素所在数组中的位置一一对应。比如0放在下标为0的位置，1放在下标为1的位置......以此类推。然后要求出最小的交换次数。
我一开始想到的就是用暴力，先用个变量pos来记录‘0‘的下标位置，然后遍历数组找到元素值为pos的那个元素的下标位置，最后交换，同时把pos更新为那个进行交换的下标位置。
当然，在这个过程中‘0‘可能会被交换到‘0‘这个下标位置，这时只要遍历一遍数组，找到不匹配的元素（元素与对应位置下标不相同），进行交换就可以了，然后再次重复上述的步骤。
当遍历数组时发现每个元素都已经匹配了，就结束这个过程，输出交换的次数。
相应的代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 4 int main() { 5 int n, pos, cnt = 0; 6 scanf("%d", &n); 7 int a[n]; 8 for (int i = 0; i < n; i++) { 9 scanf("%d", a + i); 10 if (a[i] == 0) pos = i; 11 } 12 13 while (true) { 14 int i; 15 if (pos) { 16 for (i = 0; i < n; i++) { 17 if (a[i] == pos) break; 18 } 19 } 20 else { 21 for (i = 0; i < n; i++) { 22 if (a[i] != i) break; 23 } 24 if (i == n) break; 25 } 26 std::swap(a[i], a[pos]); 27 pos = i; 28 cnt++; 29 } 30 31 printf("%d", cnt); 32 33 return 0; 34 }
提交结果如上，并没有AC，而是TLE。因为这种暴力解法的时间复杂的很高，每次交换都要遍历数组来找到要交换的元素，这很耗时。
所以我们应该改进算法。
其实这个题目可以理解为：给定N个数字的排列，如何仅利用与‘0‘交换达到排序的目的。
当我们看到N个数字的排列时，应该想到有这样一条结论：N个数字的排列由若干个独立的环组成。
关于这个结论我在知乎上看到很棒的解答，这里就直接引用大佬的回答了：
作者：grayMeerkat
链接：https://www.zhihu.com/question/453165129/answer/1820578572
来源：知乎
灵剑大佬的解答很完整了，我用图再说明一下
对于包含 n 个数的序列，可以构造一个有向图，如果数字 x 在序列里第 y 个位置上，则在图上添加一条由 x 指向 y 的边
比如序列 543621 对应下图，可以看到 16425 构成了一个环，而数字 3 就在第 3 个位置，表示为一个孤立的点
设序列中有两个数 a 和 b，其中 a 在第 p 个位置上，b 在第 q 个位置上，则它们要么在同一个环里，要么不在同一个环里
如果 a 和 b 不在同一个环里，则它们在图中的一种情况如下（其他情况也是类似的，包括 a 等于 p、b 等于 q 的情况）：
如果在序列里交换 a 和 b，则 a 的位置由 p 变成了 q，b 的位置由 q 变成了 p，图中其他点的位置不变，因此只需要在图中把 a 改为指向 q，b 改为指向 p，得到：
可以看到两个环变成了一个，也就是说环的数量减少了 1 个
而如果 a 和 b 原本在同一个环里，交换 a 和 b 会让图中的环增加 1 个，比如从
变成
(这里也有特殊情况，比如 a 直接指向 b，不过结果也是一样的）
由于每次交换最多只能让环的数量增加 1 个，而我们最终的目标序列对应的是 n 个孤立的点（单个点也可以看作一个环），因此只有最初让所有点共同构成一个完整的环，才能使得所需的交换次数达到 n - 1
此时问题就转化成了：n 个点构成一个环，有多少种不同的方式。由于两个旋转后重合的环也算是同一个环，因此不妨把数字 1 固定，然后求出剩下 n - 1 个数的排列，也就是 (n - 1)!
而 n 个数构成的不同序列一共有 n! 种，因此最终的答案为 1 - (n - 1)! / n! = (n - 1) / n
这道题目是用‘0‘与其他元素进行交换的，所以相应的环有3种：
说了这么多，现在我们回到题目上，来看看代码应该怎么写。
之前我们是按照输入的顺序来把元素存放到数组中的，现在我们变聪明些，我们用数组pos来存放元素的位置，这样数组的下标就是元素的值，存放的是该元素的位置。
然后我们利用上面所说的环来对元素进行交换排序，这里举个简单的例子帮助理解。
’0‘放在哪个位置？哦，’0‘的位置就是pos[0]。只要pos[0] != 0就说明‘0‘在某一个环中，这时我们只需要不断对这个环中的元素进行交换，把所有的元素都交换到相应的位置，那么该环的元素就完成匹配了。
而当pos[0] == 0时，我们要把‘0‘加入到另一个还没有完成匹配的环中，这样就可以把这个环中的元素通过交换放到数组对应的位置。
怎么找到这个还没有匹配完成的环呢？很简单，只要在遍历数组时发现a[i] != i，就进行一次交换std::swap(pos[0], pos[i])，就可以把‘0‘加入到这个环中。
所以，这种思路的代码如下：
1 #include <cstdio> 2 #include <algorithm> 3 4 int main() { 5 int n, cnt = 0; 6 scanf("%d", &n); 7 int pos[n]; // pos数组存放的是元素的位置 8 for (int i = 0; i < n; i++) { 9 int num; 10 scanf("%d", &num); 11 pos[num] = i; 12 } 13 14 for (int i = 1; i < n; i++) { // 只需要从头遍历数组一次，就可以实现把元素交换放到对应的位置 15 if (pos[i] != i) { // 元素的值不等于数组下标，说明存在一个环，环中的元素都没有完成匹配 16 if (pos[0] == 0) { // 如果发现pos[0] == 0，就把元素0通过交换加入到这个环中 17 std::swap(pos[0], pos[i]); 18 cnt++; // 把元素0加入环也要计数 19 } 20 // 不断循环，通过元素0把这个环中的元素都交换放在对应的位置，当pos[0] == 0时说明了这个环的元素已经完成匹配了 21 while (pos[0] != 0) { 22 std::swap(pos[0], pos[pos[0]]); 23 cnt++; 24 } 25 } 26 } 27 printf("%d", cnt); 28 29 return 0; 30 }
总结一下，其实这种思想和表排序的很像。其实就是交换元素的下标而不交换元素本身。
如何解决下面这道有关数字排序的问题？：https://www.zhihu.com/question/453165129
1067. Sort with Swap(0,*) (25)-PAT甲级真题（贪心算法）：https://www.liuchuo.net/archives/2301
浙江大学——数据结构：https://www.icourse163.org/course/ZJU-93001?tid=1461682474
原文：https://www.cnblogs.com/onlyblues/p/14804900.html
