首先，感谢楼上给予这种思路。在这个思路的基础上，使用一个数组记录各个数据的下标，就不必查找。于是就将复杂度降为O(n)。
int num[10001];
int index[10001];

void init(int n)
{
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&num[i]);
		index[num[i]] = i;
	}
}

inline void Swap(int &a,int &b)
{
	int t = a;
	a = b;
	b = t;
}

int getRes(int n)
{
	int i,t,sum=0;
	for(i=1;i<=n;i++)
	{
		if(num[i] != i)
		{
			sum ++;
			t = num[i];
			Swap(num[i],num[index[i]]);
			Swap(index[i],index[t]);
		}
	}
	return sum;
}

• Re:同一解法 (296) zhangfeifei 2010-08-23 21:14:29