CodingInterviewChinese2
CodingInterviewChinese2 copied to clipboard
zhedahht
面试题3:数组中重复的数字 题目一
最后一种解法，第二版书中指出 “代码中尽管有一个两重循环，但每个数字最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。”
这句话中提到的每个数字最多只要交换两次是否欠妥？比如原数组是[1,2,3,4,5,0]的情况，第一个元素要同后面元素依次交换，也就是5次才能把0放到正确的位置。可是总的又只需要5次交换就够了，但是最差的情况是不是需要交换n + (n-1) + (n-2) + ...+ 1次，所以时间复杂度就是O(n^2)。
书本中这句话的确描述有问题。 我认为书本上应该修改为 “代码中尽管有一个两重循环，但每个数字《《平均》》最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。” 这里应该是每个数字平均最多交换两次就行。 通过举例分析我们可以知道，0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置；而对于有重复数字的数组，这个值小于n-1。那么平均到每个数字其移动次数为n/(n-1)。由于n为自然数，因此这个公式的最大值为2。
书本中这句话的确描述有问题。 我认为书本上应该修改为 “代码中尽管有一个两重循环，但每个数字《《平均》》最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是O(n)。” 这里应该是每个数字平均最多交换两次就行。 通过举例分析我们可以知道，0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置；而对于有重复数字的数组，这个值小于n-1。那么平均到每个数字其移动次数为n/(n-1)。由于n为自然数，因此这个公式的最大值为2。
大佬，我用100000个数据测试了下，“0~(n-1)这个n个数字在没有重复数字的情况下最多需要交换n-1次就可以让所有数字找到自己的位置”这句话，最多应该是交换n次。
书本中这句话的确描述有问题。 我认为书本上应该修改为 “代码中尽管有一个两重循环，但每个数字《《平均》》最多只要交换两次就能找到属于它自己的位置，因此总的时间复杂度是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） 由以上可以举例归纳后可以得出我上面提到的结果。
长度为n，值为0到n-1且不重复的数组最多需要n次交换 因为交换的过程是判断当前位置i上的数值m是否等于i，如果相等，说明i位置上的元素是正确的，就i+1。 如果不相等，就和位置m上的元素进行交换，交换结束后，位置m上的元素一定是正确的。 一共有n个位置，每次交换保证一个位置上元素正确，所以，一共最多n次交换。
长度为n，值为0到n-1且不重复的数组最多需要n次交换 因为交换的过程是判断当前位置i上的数值m是否等于i，如果相等，说明i位置上的元素是正确的，就i+1。 如果不相等，就和位置m上的元素进行交换，交换结束后，位置m上的元素一定是正确的。 一共有n个位置，每次交换保证一个位置上元素正确，所以，一共最多n次交换。
n-1次交换后可以确保n-1个位置上的元素位置正确，那么剩下的一个元素位置也能确定是正确的。
