找出重复的数字

果子

[bgcolor=#ffffff]问题：数组a[N]，1至N-1这N-1个数存放在a[N]中，其中某个数重复一次。写一个函数，找出被重复的数字。时间复杂度不超过O(n)。[/bgcolor]

果子

解题思路：

设数组a[n] = {2,3,2,1}，2是重复数字。
把一个数组b[]初始化为"0000"，对a[]访问一位在b[]上标记一位，再次访问到时查看标志位已经被置1则发现重复。空间复杂度O(n)。
遍历时，a[0]=2，令b[2]=1，"0010"；a[1]=3，令b[3]=1，"0011"；a[2]=2，b[2]已经==1，找到a[2]。