leetcode 287 寻找重复数

题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
示例 3：

输入：nums = [1,1]
输出：1
示例 4：
输入：nums = [1,1,2]
输出：1
提示：
2 <= n <= 3 * 104
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以在不修改数组 nums 的情况下解决这个问题吗？
你可以只用常量级 O(1) 的额外空间解决这个问题吗？
你可以设计一个时间复杂度小于 O(n2) 的解决方案吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

1. 二分法

由于 n在[1, n + 1]区间 有 n + 1 个数，所以，

我们不要考虑数组,只需要考虑 数字都在 1 到 n 之间
        示例 1:
        arr = [1,3,4,2,2] 此时数字在 1 — 5 之间
        mid = (1 + 5) / 2 = 3 arr小于等于的3有4个(1,2,2,3)，1到3中肯定有重复的值
        mid = (1 + 3) / 2 = 2 arr小于等于的2有3个(1,2,2)，1到2中肯定有重复的值
        mid = (1 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值
        所以重复的数是 2

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
    // 利用数字都在 1- n 之间进行二分法 
    // 只要找 n >> 1 左右两半边的数> n >> 1 的即为右重复数的一半
    const n = nums.length
    let l = 1, r = n
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        let count = 0
        for (let n of nums) {
            if (n <= mid) {
                count++
            }
        }
        if (count <= mid) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l


    // // dp + 二分
    // const n = nums.length
    // const dp = new Array(n)
    // let maxL = 0
    // for (let i = 0; i < n; i++) {
    //     let l = 0, r = maxL
    //     while (l < r) {
    //         const mid = l + ((r - l) >> 1)
    //         if (dp[mid] < nums[i]) {
    //             l = mid + 1
    //         } else {
    //             r = mid
    //         }
    //     }
    //     if (dp[l] === nums[i]) {
    //         return nums[i]
    //     }
    //     dp.splice(l, 0, nums[i])
    //     maxL++
    // }
};

2.快慢指针
类似于链表找环
思路，将数组抽象为链表，问题转化为 寻找链表环入口
如何寻找链表环入口

1. 先用快慢指针找到交点（可能在环的任何一处）
2. 将快指针移动到链表开头，快慢同时走，交点即为环入口

[b]证明

定义：slow => s, fast => f, 环长 m
s = x + k
f = x + m * n + k

而 快指针速度是慢指针的两倍
f = 2 s
=> 2(x + k) = x + m n + k
=> x = m *n - k
若 n === 1 => x = n - k
即 交点再走 n-k 步 === 从开头走 x 步

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function (nums) {
    //寻找链表环的入口
    let s = 0, f = 0
    while (true) {
        s = nums[s]
        f = nums[nums[f]]
        if (s === f) {
            f = 0
            while (s !== f) {
                s = nums[s]
                f = nums[f]
            }
            return s
        }
    }
};