题目描述

找出数组中重复的数字。

在一个 长度为 n 的数组 nums 里的 所有数字都在 0～n-1 的范围 内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中 任意一个重复的数字 。
示例 1：

输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 

该题目的难度级别为 Easy。

思路 1

最直观的方式可能就是排序 + 遍历的方式, 根据这个思路可以很容易的写出代码

def findRepeatNumber(nums: List[int]) -> int:
    if nums == None or len(nums) < 2:
        return 
    nums.sort()
    
    for i in range(1, len(nums)):
        # 只要找到就可以返回
        if nums[i] == nums[i-1]:
            return nums[i]

排序的时间复杂度为 $O(nlogn)$, 遍历的时间复杂度为 $O(n)$, 即算法的时间复杂度为 $O(nlogn)$, 空间复杂度为 $O(1)$。

思路 2

使用字典作为计数器，只要某个元素的已经存在于字典中就可以直接返回。按照这个思路可以写出如下代码

def findRepeatNumber(nums: List[int]) -> int:
    if nums == None or len(nums) < 2:
        return 
    dicts = {}
    
    for i in nums:
        # 只要找到就可以返回
        if i in dicts:
            return i
        dicts[i] = 1

相比于第一种算法，该算法以空间换时间。因为只有一次循环，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

优化算法

上面 2 中思路都是比较容易想到的，那么有没有不使用额外空间，并且时间复杂度为 $O(n)$ 的算法呢。

每次换一种思路时，我们需要重新去思考题目，而不是在已有的思路上纠结。
如果数组 nums 没有重复，那么 nums 的索引所构成的集合和 nums 中的元素构成的集合是相等的 (从集合的角度上来看，不考虑顺序)。 即对于任意一个索引，都有唯一的元素与它相等，相对应。

但如果 nums 包含重复元素，那么 对于部分索引，将会对应多个相同元素，比如 nums = [2, 3, 1, 0, 2, 5, 3]

索引为 2 的对应数组中的 2 个 2，索引为 3 的对应数组中的 2 个 3。我们可以依次的将每个元素放到它对应的索引位置，而如果该元素和它对应索引位置的元素相等，说明该元素重复。

按照这个思路，可以写出如下的代码

def findRepeatNumber(nums: List[int]) -> int:
    if nums == None or len(nums) < 2:
        return 
    for i in range(len(nums)):
        # 索引和对应元素不一致，调整元素位置，直至索引与元素匹配或者找到重复元素
        while i != nums[i]:
        
            # 如果当前元素对应的索引位置的值与当前元素相等
            if nums[i] == nums[nums[i]]:
                return nums[i]
                
            # 交换 nums[i]和 i 位置的值
            temp = nums[i]
            nums[i], nums[temp] = nums[temp], nums[i]

上述代码虽然包含了 2 次循环，但每个位置都可以在有限次内结束。因此总的时间复杂度为 $O(n)$，并不需要使用额外的空间，空间复杂度为 $O(1)$。

总结

经历了惨痛的教训，终于决定要开始认真刷题了。之前一直是处于间歇期放弃的状态，导致现在基本上是从零开始了。
我会尽可能把自己做过的题目进行一些总结，由于本人对于数据结构和算法的学习有限，大佬勿喷。