题目描述
Given any permutation of the numbers {0, 1, 2,..., N-1}, it iseasy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed touse? 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 givenpermutation of the first N nonnegative integers.
输入描述:
Each input file contains one test case, which gives a positive N(<=105) followed by a permutation sequenceof {0, 1, ..., N-1}. All the numbers ina line are separated by a space.
输出描述:
For each case, simply print in a line the minimum number ofswaps need to sort the given permutation.
输入例子:
10 3 5 7 2 6 4 9 0 8 1
输出例子:
9
这一题使用了一种方法，就是检查0的位置是否在0，如果不在0，就和应该在这个位置的数字交换位置，如果0在0，就和第一个不在其本身位置的数交换位置
这种方法的具体原理我还不清楚，不过貌似是使用的贪心算法思想
这一题还有一点需要注意的就是，假如没有找需要和0交换位置的数的时候都重新遍历一遍数组的话，那么时间为O(n^2)，这样会超时吗，所以需要维护一个numIndex数组，numIndex[i]表示数字i在原数组中的位置，然后维护一个index，index是第一个不在其本身位置上的数的位置，index左边的数除了0以外全部都在其本身的位置上，
这样每次将0和其他数交换位置的时候，同一时间也更新numIndex数组，如果发现index位置的数是Index,那么index右移，直到找到新的index，
这样的话时间复杂度会非常大的降低
#include <iostream>#include <algorithm>using namespace std;int num[100003];int numIndex[100003];void swapTheIndex(int indexOne,int indexTwo){swap(num[indexOne],num[indexTwo]);swap(numIndex[num[indexOne]],numIndex[num[indexTwo]]);}int main(){int N;int indexOne,indexTwo;int index=1;int count=0;cin>>N;for(int i=0;i<N;i++){cin>>num[i];numIndex[num[i]] = i;}while(index<N&&num[index] == index ) index ++;while(index<N){if(numIndex[0] != 0 ){indexOne=numIndex[0];indexTwo = numIndex[numIndex[0]]; swapTheIndex(indexOne,indexTwo);count++;if(num[index] == index)while(index<N&&num[index] == index ) index ++;}else{indexOne = 0;indexTwo = index;swapTheIndex(indexOne,indexTwo);count++;}}cout<<count;return 0;}