題目描述
在一個長度為 n 的數(shù)組 nums 里的所有數(shù)字都在 0～n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復的，但不知道有幾個數(shù)字重復了，也不知道每個數(shù)字重復了幾次。請找出數(shù)組中任意一個重復的數(shù)字

示例
輸入：
[2, 3, 1, 0, 2, 5, 3]
輸出：2 或 3

限制：
2 <= n <= 100000

解題思路：
首先初始化定義一個全0的數(shù)字列表，這個列表的索引下標可以作為輸入值，具體列表值作為數(shù)字重復次數(shù)。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        isRepeat = [0]*len(nums)
        for x in nums:
            isRepeat[x] += 1
        for i,j in enumerate(isRepeat):
            if j > 1:
                return i

Leetcode上的其他兩種解法

• 哈希表 / Set

class Solution:
    def findRepeatNumber(self, nums: [int]) -> int:
        dic = set()
        for num in nums:
            if num in dic: return num
            dic.add(num)
        return -1

復雜度分析：
時間復雜度 O(N)： 遍歷數(shù)組使用O(N) ，HashSet 添加與查找元素皆為 O(1)。
空間復雜度 O(N)： HashSet 占用O(N)大小的額外空間

• 原地交換
  
  image.png
  
  遍歷中，第一次遇到數(shù)字 x時，將其交換至索引 x處；而當?shù)诙斡龅綌?shù)字 x時，一定有 nums[x] = x，此時即可得到一組重復數(shù)字。

class Solution:
    def findRepeatNumber(self, nums: [int]) -> int:
        i = 0
        while i < len(nums):
            if nums[i] == i:
                i += 1
                continue
            if nums[nums[i]] == nums[i]: return nums[i]
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        return -1

復雜度分析：
時間復雜度 O(N)： 遍歷數(shù)組使用 O(N)，每輪遍歷的判斷和交換操作使用 O(1)。
空間復雜度 O(1)： 使用常數(shù)復雜度的額外空間。