这个array是a[1],a[2],...,a[n].假设一开始a[k]=k,目的是通过常数个变量和O(n)时间让a[k]=f(k).这里f(k)是某个一一对应函数。
假设f(k)及其反函数g(k) (对任何k=1,2,...n都有f(g(k))=g(f(k))=1)都可以通过O(1)的计算得出。如果这点不成立,肯定没有O(n)的算法(假设在大于1的循环中的数有O(n)个)
下面的大致算法:
for(k=1;k<=n;k++)
{
if(a[k]==f(k)) continue; //该数(以及所在的循环)已经满足条件了
//不符合条件的k是某个循环里第一个(最小的)不正确的数
for(t=k;f(t)!=k;t=f(t))
{
a[t]=f(t);
}
a[t]=k;
//经过这个操作,k所在的循环的所有数字都到了最终要求的位置。
}
除了个数为1的循环,所有循环都被置换一次,也就是任何一个k都只被置换一次。每个置换之前有一个O(1)的判断,所以总数还是O(n),而变量只有两个。