数组中重复的数字

题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路1:最容易想到的方法，使用额外数组或者哈希表存储。

def duplicate(self, numbers, duplication):
    # write code here
    '''
    l = []
    for i in numbers:
        if i not in l:
            l.append(i)
        else:
            duplication[0] = i
            return True
    return False
    '''
    n = len(numbers)
    boo = [0]*n
    for i in numbers:
        if boo[i] == 0:
            boo[i] = 1
        else:
            duplication[0] = i
            return True
    return False

思路2（转自 牛客网BoTinker）：十分巧妙的方法，充分利用了题目的信息。不需要额外的数组或者hash table来保存，题目里写了数组里数字的范围保证在0 ~ n-1 之间，所以可以利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。

n = len(numbers)
for i in range(n):
    index = numbers[i]
    if index >= n:
        index -= n
    if numbers[index] >= n:
        return index
    numbers[index] = numbers[index] + n
return -1