在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
要求：时间复杂度O(n)，空间复杂度O(1)。
算法思想：可以看做是一种原地哈希，不过没有用到字典。具体做法就是因为题目中给的元素是 < len（nums）的，所以我们可以让 位置i 的地方放元素i。如果位置i的元素不是i的话，那么我们就把i位置的元素放到它应该在的位置，即 nums[i] 和nums[nums[i]]的元素交换，这样就把原来在nums[i]的元素正确归位了。如果发现 要把 nums[i]正确归位的时候，发现nums[i]（这个nums[i]是下标）那个位置上的元素和要归位的元素已经一样了，说明就重复了，重复了就return。
测试用例 输入：[2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
class Solution: def findRepeatNumber(self, nums) -> int: n = len(nums) # 元素个数 for i in range(n): # 对ｎ个位置的元素进行扫描 # 若i位置放的不是i元素，需要将i位置的元素放到其该在的位置 # while循环的原因是交换元素后i位置仍可能不是i元素，需继续交换 while i != nums[i]: if nums[i] == nums[nums[i]]: # 在交换前需判断nums[i]位置处的元素是否是nums[i]本身 # nums[i]位置处的元素是nums[i]本身，则此时i位置的元素与nums[i]位置的元素重复，已找到重复元素 return nums[i] # 返回重复的元素 nums[nums[i]], nums[i] = nums[i], nums[nums[i]] # i位置的元素与nums[i]位置的元素进行交换 # 注意这里不要写成nums[i], nums[nums[i]] = nums[nums[i]], nums[i]，会出错，原因不清 if __name__ == '__main__': import ast input_ = ast.literal_eval(input().strip()) test = Solution() result = test.findRepeatNumber(input_) print(result) """ 运行结果： [2, 3, 1, 0, 2, 5, 3] 2 Process finished with exit code 0 """[题目来源于剑指offer]
