287. Find the Duplicate Number

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number}
 */

题目给我们一个数字数组 nums，其中所有数字都在 [1, n] 的范围内，其中 n === nums.length - 1

这意味着必定有一个数字是重复的，题目要求我们在 O(1) 空间复杂度与 O(n) 时间复杂度下找出这个重复的数字

解题思路

这题有两个思路，一个是类似 141 一样，用负号标识已经出现过的数字；一个是类似 142 一样，把数组当成有环的有向图并找出环的开始节点，下面我们分别讲解

用负号标识已经出现过的数字

这个方法的核心就是，在遍历数组过程中，把遍历当前元素作为下标，找到对应元素并把对应元素置为负数

如果我们遍历其他元素并以元素作为下标找到的对应元素为负，我们就知道当前元素是重复的数字了

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    for(let i=0;i<nums.length;i++) {
        const idx = Math.abs(nums[i])
        if(nums[idx] < 0) {
            return idx
        }
        nums[idx] = -nums[idx]
    }
};

把数组当成有环的有向图并找出环的开始节点

我们延续上一个解法把元素本身当成下标的想法，如果我们把数组的元素当成有向图的节点，节点的值当成他们指向的下一个节点，我们就可以获得一个有向图

由于题目保证有重复的节点，所以构成的有向图必有环，且环的开始节点下标，就是重复的数字

至此，我们可以用 142 的思路来找出环的开始节点

Javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
    const len = nums.length
    let fast = 0
    let slow = 0

    while(fast < len && nums[fast] < len) {
        fast = nums[nums[fast]]
        slow = nums[slow]
        if(fast === slow) {
            slow = 0
            while(fast !== slow) {
                slow = nums[slow]
                fast = nums[fast]
            }
            return fast
        }
    }
};