难度: Easy
设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。
示例 1：
输入：documents = [2, 5, 3, 0, 5, 0] 输出：0 或 5
提示：
0 ≤ documents[i] ≤ n-12 <= n <= 100000
Submission
运行时间: 52 ms
内存: 23.4 MB
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
for i in range(len(nums)):
while nums[i] != i:
if nums[nums[i]] == nums[i]:
return nums[i]
else:
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
return -1
Explain
此题解采用了原地哈希的思路，即利用数组本身作为哈希表使用，以达到空间效率的最大化。具体方法是通过交换数组中的元素，使得每个数字都被放置在其值对应的索引位置上。遍历数组，对于每个位置 i，如果位置 i 上的数 nums[i] 不等于 i，则说明 nums[i] 应该被放在索引 nums[i] 上。在这个过程中，如果发现索引 nums[i] 上已经存在值 nums[i]，这意味着找到了一个重复的数字。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition of the Solution class with method findRepeatNumber
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
for i in range(len(nums)):
# Continue swapping until the element at index i is not equal to i
while nums[i] != i:
# If the target position nums[i] has the same value as nums[i], a duplicate is found
if nums[nums[i]] == nums[i]:
return nums[i]
# Otherwise, swap nums[i] with the element at its target position
else:
nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
# If no duplicate is found (not expected as per problem statement)
return -1
Explore
在算法中，目标是将每个元素放置到其值对应的索引位置。如果在尝试将`nums[i]`放到它应该去的位置`nums[nums[i]]`时，发现`nums[nums[i]]`已经是`nums[i]`，说明在`nums[i]`索引位置已经有一个`nums[i]`存在，因此`nums[i]`是重复的。继续交换并不会改变这一发现，而是可能导致无限循环，因此当发现这种情况时，算法停止并返回重复的值。
此算法通过尝试将每个数字放到其值所对应的索引位置上来寻找重复。一旦在某个位置发现已经有与要放置的数字相同的值，就立即返回那个数字。如果数组中有多个重复的数字，算法返回遇到的第一个重复数字。此算法不保证总是返回所有重复数字中的特定一个，只保证返回任一遇到的重复数字。
如果数组已经是有序的且每个数字都在正确的位置上（即`nums[i] == i`对所有i成立），这意味着没有重复的数字存在，每个数字都唯一地占据了其索引位置。在这种情况下，算法在遍历过程中不会进行任何交换操作，也不会找到任何重复的数字。然而，题目的前提是存在至少一个重复的数字，所以这种情况在题目给定的背景下不会出现。
如果`nums[i]`的值不在0到n-1的范围内，会存在数组越界的风险，因为程序会尝试访问不存在的索引。因此，算法的安全执行依赖于所有元素值都必须在这个范围内。在实际应用中，应在算法开始前添加检查以保证所有元素值都在合法范围内，或在实现中处理这种异常情况，以避免越界错误。