fueanta

Find the Duplicate Number (Leetcode: 287)

Mar 17th, 2020
143
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate
  2. # number must exist. Assume that there is only one duplicate number, find the duplicate one.
  3.  
  4. # You must not modify the array (assume the array is read only).
  5. # You must use only constant, O(1) extra space.
  6. # Your runtime complexity should be less than O(n2).
  7. # There is only one duplicate number in the array, but it could be repeated more than once.
  8.  
  9. class Solution:
  10.     def findDuplicate(self, nums: List[int]) -> int:
  11.         sp = nums[nums[0]]
  12.         fp = nums[nums[nums[0]]]
  13.        
  14.         while sp != fp:
  15.             sp = nums[sp]
  16.             fp = nums[nums[fp]]
  17.        
  18.         fp = nums[0]
  19.        
  20.         while sp != fp:
  21.             sp = nums[sp]
  22.             fp = nums[fp]
  23.        
  24.         return fp
RAW Paste Data