01-数组中重复的数字

题目

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2，3, 1， 0， 2， 5， 3}，那么对应的输出是重复的数字2或者3。

思考

排序，从头扫描，时间复杂度为。

哈希表。遍历所有数字，如果这个数字没有在表中，加入表；如果在表中，则找到重复数字。时间复杂度和空间复杂度都是。

考虑in-place方法，空间复杂度是，时间复杂度？
——下标定位元素

• 从头到尾扫描这个数组中的每个数字；
• 扫描到下标为i的数字m时：
  • 这个数字m == i，扫描下一个数字；
  • 如果m != i，
    • 把m放在属于他的位置上
    • 原本属于他的位置和m相等，则m是重复数字

代码

def duplicate(nums: List[int]):
    for i, num in enumerate(nums):
            while i != nums[i]:
                # 交换num[nums[i]], num[i]
                if nums[i] != nums[nums[i]]:
                    temp = nums[i]
                    nums[i] = nums[temp]
                    nums[temp] = temp
                    # print(nums)
                else:
                    return num