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 uses only constant extra space.
Example 1: Input: nums = [1,3,4,2,2] Output: 2
- code
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
slow = fast = finder = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
while finder != slow:
finder = nums[finder]
slow = nums[slow]
return finder
Python O(1) aux space by hopping. 83%+ [ w/ Hint ] - LeetCode Discuss
It’s the same thing as leetcode 142.
The length of the circle is n = x + y. The fast and slow will meet, and fast traveled m + kn + y. Slow travelled m+y. The fast is two times as fast, so m + kn + y = 2(m + y). We can get m = x + n(k-1), n(k-1) is keep running on the circle, so eventually one from the meeting point, one from the start point, they will meet at the point where the circle begins.