前往此题

解题思路

哈希表法

遍历nums，将每个值存入到哈希表中同时检查当前遍历的值是否已经存在，如果存在说明nums中有重复元素，直接返回即可。

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        maps = {}
        for n in nums:
            if n in maps: return n
            else: maps.add(n)

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

原地置换

上面的解法空间复杂度是O(N)的，可以使用原地置换法来达到O(1)。

题目中给出了在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内 ，所以我们可以通过遍历数组来置换元素进行排序，这样可以做到使nums[i] == i的效果。如果在遍历过程中遇到nums[i] == nums[nums[i]]说明遇到了重复元素，将它返回即可。

算法过程

1. 遍历数组通过交换操作使索引与值一一对应，直到nums[i] == i，交换下一个来达到排序的目的
2. 在不断交换的同时如果出现索引与值对应就说明遇到重复元素了

代码

class Solution:
    def findRepeatNumber(self, nums: List[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