287. Find the Duplicate Number
环
Given an array of integers nums
containing n + 1
integers where each integer is in the range [1, n]
inclusive.
There is only one repeated number in nums
, return this repeated number.
You must solve the problem without modifying the array nums
and using only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Example 3:
Input: nums = [3,3,3,3,3]
Output: 3
Constraints:
1 <= n <= 10
5
nums.length == n + 1
1 <= nums[i] <= n
All the integers in
nums
appear only once except for precisely one integer which appears two or more times.
分析
关键观察:
将数组索引和值看作链表节点:
索引
i
指向nums[i]
例如
nums = [1,3,4,2,2]
可转化为:CopyDownload
0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
重复数必然形成环:
因为有重复数字,必然存在至少两个索引指向同一个值
这会导致链表出现环(如示例中
2 → 4 → 2
的环)
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow, fast = 0, 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Last updated
Was this helpful?