PAT 1067 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:

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.

Input Specification:

Each input file contains one test case, which gives a positive N (≤10​5​​) 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:

10
3 5 7 2 6 4 9 0 8 1

Sample Output:

9

------------------------------- 这是题目和解题的分割线------------------------------- 

要想次数最少，必须0和0下标的数字交换。如果0交换到了0下标处，而此时还没交换完毕，则与一个不在本位的数字交换。

注意，这道题目容易超时。我最先的代码虽然表面没用二层循环，但时间复杂度也差不了多少。

//超时代码 
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
	int n,i,a[100005],pos,count = 0,num = 0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==0) pos = i;
		if(a[i]!=i&&a[i]) num++;
	}
	i = 0;
	while(num!=0)
	{
		if(pos!=0)
		{
			if(a[i]==pos)
			{
				swap(a[i],a[pos]);
				pos = i;
				num--;
				count++;
			} 
		}
		else
		{
			if(a[i]!=i)
			{
				swap(a[i],a[pos]);
				pos = i;
				count++;
			}
		}
		i++;  
		if(i==n) i = 0; //就是这两句话超时啦 
	}
	printf("%d",count);
	return 0;
} 

我的代码中这两句i++; if(i==n) i = 0导致循环次数太多，但为了找到结果为零的下标，不得已这样写。看书上的代码，换了个输入的办法，让读入的数作为数组下标，读入的数所在的位置作为数组内容，和常规相反，正好避免了找下标浪费时间的做法。

//AC代码 
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
	int n,a[100005],i,num,count = 0;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{	
		int x;
		scanf("%d",&x);
		a[x] = i; //内容和下标反过来读取 
		if(x!=i&&x) num++; 
		//除0以外不在本位的个数，因为最后一次交换会恢复两个数字的位置 
	}
	i = 1;
	//还存在不在本位的数字 
	while(num!=0)
	{
		//0不在本位的时候(a[0]是0所在的下标)
		while(a[0]!=0)
		{
			swap(a[0],a[a[0]]);
			num--;
			count++;
		}
		if(a[0]==0)
		{
			//找到不在本位的数字进行交换 
			while(i<n)
			{
				if(a[i]!=i)
				{
					swap(a[i],a[0]);
					count++;
					break;
				}
				i++;
			}
		}
	}
	printf("%d",count);
	return 0;
}