题目翻译：

给定包含n+1个整数的数组nums，其中每个整数都在1到n（包含）之间，证明必须存在至少一个重复数。假设只有一个重复的数字，找到重复的一个。

注：

1. 不能修改数组（假设数组是只读的）。
2. 只能使用常量，O(1)的额外空间。
3. 时间复杂度应该小于O(n^2)。
4. 数组里只有一个重复数字，但是这个数字可以重复多次。

题目思路1：

使用collections模块里的Counter()类得到数组里每个元素出现的次数。若出现的次数大于1，则判断为重复的数字。

代码如下：

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        import collections
        key_dict = {}
        key_dict = collections.Counter(nums)
        for key, count in key_dict.items():
            if count != 1:
                return key
            else:
                pass

题目思路2：

对数组nums进行排序，排序后的数组，若有重复数字，则两个数字应该相邻。

代码如下：

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        for i in range(0, len(nums) - 2):
            if nums[i] == nums[i + 1]:
                return nums[i]
            else:
                i += 1