Sort with Swap(0, i)
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:
1 | Swap(0, 1) => {4, 1, 2, 0, 3} |
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.
Input Specification:
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.
Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
Sample Input:
1 | 10 |
Sample Output:
1 | 9 |
题目分析
这道题是一道很明显的表排序的问题,其输出的结果就是表排序中每次环中对位置进行交换的次数
而我们需要注意的是环分三种
1.只有1个元素不需要交换
2.环里有n个元素包括0,则需要交换n-1次
3.第i个环里有n个元素,不包括0,先把0换到环里,再进行(n+1)-1次交换即n+1次交换
而这里我们可以利用一个指针数组T来存储元素i在A[T[i]]中存放,即T[A[i]]=i
,这样我们可以更加容易地找到表排序中每次交换的下一个位置
代码实现
1 |
|