面试题3:数组中重复的数字 题目一

[getaway523]

最后一种解法，第二版书中指出 “代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。”

这句话中提到的每个数字最多只要交换两次是否欠妥？比如原数组是[1,2,3,4,5,0]的情况，第一个元素要同后面元素依次交换，也就是5次才能把0放到正确的位置。可是总的又只需要5次交换就够了，但是最差的情况是不是需要交换n + (n-1) + (n-2) + ...+ 1次，所以时间复杂度就是O(n^2)。

[FishSeeker]

是的,我也想问这个问题,怎么可能是只要交换两次就能找到呢,时间复杂度分析得有点问题.

[bigbearishappy]

书本中这句话的确描述有问题。
我认为书本上应该修改为
“代码中尽管有一个两重循环，但每个数字《《平均》》最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。”
这里应该是每个数字平均最多交换两次就行。
通过举例分析我们可以知道，0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置；而对于有重复数字的数组，这个值小于n-1。那么平均到每个数字其移动次数为n/(n-1)。由于n为自然数，因此这个公式的最大值为2。

[tinyvampirepudge]

书本中这句话的确描述有问题。
我认为书本上应该修改为
“代码中尽管有一个两重循环，但每个数字《《平均》》最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。”
这里应该是每个数字平均最多交换两次就行。
通过举例分析我们可以知道，0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置；而对于有重复数字的数组，这个值小于n-1。那么平均到每个数字其移动次数为n/(n-1)。由于n为自然数，因此这个公式的最大值为2。

大佬，我用100000个数据测试了下，“0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置”这句话，最多应该是交换n次。

[bigbearishappy]

书本中这句话的确描述有问题。
我认为书本上应该修改为
“代码中尽管有一个两重循环，但每个数字《《平均》》最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。”
这里应该是每个数字平均最多交换两次就行。
通过举例分析我们可以知道，0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置；而对于有重复数字的数组，这个值小于n-1。那么平均到每个数字其移动次数为n/(n-1)。由于n为自然数，因此这个公式的最大值为2。

大佬，我用100000个数据测试了下，“0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置”这句话，最多应该是交换n次。

辛苦你专门跑了程序来验证我的结果。至于为什么实际程序跑出来是最多交换n次，我暂时还没有想到原因。
我之前在思考这个问题时使用的是归纳法得出结果的，具体步骤如下，供你参考：
n=2 buf = 0,1 当buf = 1,0 时， 需要交换1次就ok（1,0=>0,1）
n=3 buf = 0,1,2 当buf = 2,0,1时， 需要交换2次就ok（2,0,1=>1,0,2=>0,1,2）
n=4 buf = 0,1,2,3 当buf = 3,0,1,2时 需要交换3次就ok（3,0,1,2=>2,0,1,3=>1,0,2,3=>0,1,2,3）
由以上可以举例归纳后可以得出我上面提到的结果。

[wendy199909]

长度为n，值为0到n-1且不重复的数组最多需要n次交换
因为交换的过程是判断当前位置i上的数值m是否等于i，如果相等，说明i位置上的元素是正确的，就i+1。
如果不相等，就和位置m上的元素进行交换，交换结束后，位置m上的元素一定是正确的。
一共有n个位置，每次交换保证一个位置上元素正确，所以，一共最多n次交换。

[sssky246]

长度为n，值为0到n-1且不重复的数组最多需要n次交换 因为交换的过程是判断当前位置i上的数值m是否等于i，如果相等，说明i位置上的元素是正确的，就i+1。 如果不相等，就和位置m上的元素进行交换，交换结束后，位置m上的元素一定是正确的。 一共有n个位置，每次交换保证一个位置上元素正确，所以，一共最多n次交换。

n-1次交换后可以确保n-1个位置上的元素位置正确，那么剩下的一个元素位置也能确定是正确的。