LeetCode: 287. Find the Duplicate Number

LeetCode: 287. Find the Duplicate Number

题目描述

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

解题思路

1. 将数组的索引作为地址，存入数组的元素作为值，每个数组单元作为一个节点
2. 由于不存在值为 0 的节点，因此构成的节点一定不会在首节点形成环
3. 由于值中存在重复元素，因此构成的链表一定存在重复的节点指向同一个节点，构成环。（一个进入环，一个形成环）
4. 环的入口即是重复元素
5. 查找环入口的方式见 ​​LeetCode: 142. Linked List Cycle II 题解​​

举个栗子

1. 求如图数组的重复元素
2. 将数组拆分成节点， 索引作为地址， 值作为 next 指针
3. 将节点连接成链表
   
   整理之后，如下图：
4. 环的入口 5， 即是重复元素

AC 代码

func findDuplicate(nums []int) int {
    if len(nums) == 0 { return 0 }
    
    // 找环
    fast := nums[nums[0]]
    slow := nums[0]
    for fast != slow {
        fast = nums[nums[fast]]
        slow = nums[slow]
    }
    
    // 找环的入口
    newSlow := 0
    for newSlow != slow {
        newSlow = nums[newSlow]
        slow = nums[slow]
    }
    
    return slow
}