Yang Shuqi

Find the Duplicate Number

 

    287. Find the Duplicate Number

    Solution

    1. Consider the array as a linked list.

    2. The existence of the duplicate number shows the existence of the cycle in the linked list.

    3. The entrance of the cycle is the duplicate number.

    def findDuplicate(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    slow = nums[0]
    fast = nums[nums[0]]
    
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
        
    fast = 0
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow
    Search