题目描述

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

算法

(数组遍历) $O(n)$

一个简单的思路，就是把nums中所有数字的出现次数都记录下来，返回第一个次数大于0的即可。
首先，我们需要一个列表li用来存放数字出现次数，由题得数字在0~n-1之间，因此li的长度与nums相等，li[i]即表示数字i在nums中出现的次数；
然后，遍历数组nums，判断数字在0~n-1范围内，不满足的话不符合题目要求，返回-1，满足的话再累计数字出现的次数；
最后，遍历完数组nums后，输出li列表中任意一个li[i]大于0的下标i。
OVER!!!

时间复杂度分析：整个下来，我们的操作有：初始化一个列表、遍历一个长度为n的数组、在长度为n的列表中查找大于0的值，因此最坏的情况也是2n，同数量级$O(n)$

Python3 代码

class Solution(object):
    def duplicateInArray(self, nums):
        """
        :type nums: List[int]
        :rtype int
        """
        # 获取列表的长度
        length = len(nums);
        # 初始化一个长度为length的列表
        li = [0]*length;
        # 遍历列表中的值，i为列表中的元素值
        for i in nums:
            if i < 0 or i > length - 1:
                return -1
            li[i] += 1;
        # i为0~length-1
        for i in range(length):
            if li[i] > 1:
                return i
        return -1