面试题——找出1000个连续数中出现的一个重复数

前些天去面试一家做ipad开发的公司，第一道题是找出1000个数（1-999）中一个重复的数。这1000个数是连续且乱序的。我的第一反应就是创建一个999的数组，然后根据数字找相应的数组下标，如果对应的为空则填充，如果有值则找到了重复的数。python版的解法如下：

# 创建测试数据，1000个数，随机排序，为了简单用了0-999

lst = range(1000)for i in range(500): pos1 = randint(0, 999) pos2 = randint(0, 999) lst[pos1], lst[pos2] = lst[pos2], lst[pos1]pos1 = randint(0, 999)pos2 = randint(0, 999)lst[pos1] = lst[pos2]print 'repeat number is: ', lst[pos1]

# 使用数组的方式查找

tmp_lst = [-1 for i in range(1000)]for n in lst: if n == tmp_lst[n]: print 'method 1 find: ', n else: tmp_lst[n] = n

该方法是时间复杂度最低的，但是空间复杂最高。面试过后才想明白其实存储那1000个数的数组（这里是lst）本身就是存储空间，我无须再创建一个临时的1000数组。只要创建一个用于保存临时交换数字的空间就可以了。解题思路还和上面一样，按照数字与数组下标的对应关系，来填充到相应位置。只是每一次填充过程都是一个系列替换过程，比如[2,1,3,0]这样的数组，拿到第一个数字式2，则将[2]中的3保存到临时变量中，然后[2]=2，然后再将[3]中的0保存在临时变量中[3]=3，然后将[0]=0。这样一个交换过程就完成了。

num = -1pos = -1for i in range(1000): num = lst[i] # 如果下标与其中的值相同则跳过 if i == num: continue else: while num != i: if num == lst[num]: pos = i print 'method 2 find: ', num break lst[num], num = num, lst[num] lst[i] = num