面试题3 数组中重复的数字

[ghost]

第二版书中41页提到，"虽然有两个循环，但每个数字最多只要交换两次就能找到属于它自己的位置，所以总时间复杂度是O(n)"

这里不太明白，书中给的例子第一个下标就交换了三次，这个O(n)是怎样得出的呢？

[zhedahht]

从0到n-1里面的任意一个数字i，如果开始它不在下标为i的位置，通过交换把它放到下标为i的位置。如果下次再遇到值为i的数字，当我们再想把它交换到下标为i的位置时，就会发现下标为i的位置已经有一个值为i的数字，就找到一个重复的数字了。

我们通过这这种交换，把从0到n-1的每个数字都放到和值相等的下标的位置。一个数字最多只需要交换两次。所以交换的次数是O(n)。

[ghost]

明白了，谢谢。