数组中重复的数字

题目描述

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

思路：

如果对于重复数字大小没有要求的话，可以直接利用哈希值进行判断。遍历数组，当前元素如果已经存放在哈希表的key中，则说明是重复的数字，将其返回。

以下为代码

def duplicate(self, numbers, duplication):

    #import collections

    # write code here

    flag = False

    n = len(numbers)

    if n <= 0:

        return flag

    numbers.sort()

    dic = {}

    for num in numbers:

        if num in dic.keys():

            flag = True

            duplication[0] = num

            break

        else:

            dic[num] = 1

    return flag