问题
在一个长度为n
的数组里的所有数字都在0
到n-1
的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7
的数组{2,3,1,0,2,5,3}
,那么对应的输出是第一个重复的数字2
。
理解
看到这种找重复数字的题目,第一反应是先将数组排序,然后在已序数组中查找重复数字。排序一个长度为n
的数组需要$O(nlogn)$的时间,之后再遍历数组。
同样,我们也可以利用哈希表来解决这个问题。从头到尾按顺序扫描原数组,每扫描一个数字,判断哈希表中是否存在该数字,若没有该数字,就将数字加入哈希表中,若哈希表中已存在该数字,则就找到一个重复数字。
当然,今天所要讲解的方法并不是以上两个。
我们注意到,数组中的数字都在0~n-1
范围内。如果这个数组中没有重复的数字,那么当数组排序后,数字i
就会出现在索引为i
的位置上。但是现在是数组中有重复的数字,有些位置上可能存在多个数字,有些位置上没有数字。
从头到尾扫描这个数组中的每个数字,当扫描到下标为i
的数字时,
- 首先比较这个数字(记为
m
)和i
是否相等,若相等,接着扫描下一个数字; - 若不相等,则将
m
与索引为m
上的数字进行比较。- 如果它与第
m
个数字相等,就找到了一个重复的数字; - 若不相等,则将第
i
个数字和第m
个数字交换,把m
放在属于它的位置上。
- 如果它与第
- 接下来便是重复比较下去,直到发现一个重复的数字。
代码
|
|