[LeetCode] 287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:
Input: nums = [1,3,4,2,2]
Output: 2

Example 2:
Input: nums = [3,1,3,4,2]
Output: 3

Example 3:
Input: nums = [3,3,3,3,3]
Output: 3

Constraints:
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:
How can we prove that at least one duplicate number must exist in nums?
Can you solve the problem in linear runtime complexity?

寻找重复数。

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

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

思路一 - 二分法

注意数组是无序的。当得到数组长度 len 和数组长度的一半 mid 之后，用 count 记录有多少个数小于等于中间数 mid。举个例子，如果数组长度是 10，mid 则是 5，这里 mid 指的是数组长度的一半。如果小于 mid 的个数大于数组的一半，说明重复的数字一定是小于 mid 的；反之如果大于 mid 的个数过半，重复的数字一定是大于 mid 的。用二分法逐渐逼近这个值，注意 return 的是 left。

复杂度

时间O(nlogn) - 二分 logn * 每次找到 mid 之后要再把所有元素看一遍
空间O(1)

代码

Java实现

class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        // 因为数字的范围就是从1开始的，所以这里不是0，是1
        int left = 1;
        int right = len - 1;
        while (left <= right) {
            // 在 Java 里可以这么用，当 left + right 溢出的时候，无符号右移保证结果依然正确
            int mid = left + (right - left) / 2;
            int count = 0;
            for (int num : nums) {
                if (num <= mid) {
                    count++;
                }
            }
            // 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个
            // 此时重复元素一定出现在 [1, 4] 区间里
            if (count > mid) {
                // 重复元素位于区间 [left, mid]
                right = mid - 1;
            } else {
                // if 分析正确了以后，else 搜索的区间就是 if 的反面
                // [mid + 1, right]
                left = mid + 1;
            }
        }
        return left;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let start = 1;
    let end = nums.length - 1;
    while (start < end) {
        let middle = Math.floor((start + end) / 2);
        let count = 0;
        // 计算总数组中有多少个数小于等于中间数
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] <= middle) {
                count++;
            }
        }

        if (count <= middle) {
            start = middle + 1;
        } else {
            end = middle;
        }
    }
    return start;
};

思路二 - 快慢指针

这个思路很难想到，参考 142 题。因为数组一定是有重复数字出现而且数字的范围不大于数组的长度，所以可以用快慢指针的思路做。当快慢指针相遇之后，再走第二遍，再次相遇的地方就是环的起点，也就是重复的数字。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int findDuplicate(int[] nums) {
        int len = nums.length;
        if (len > 1) {
            int slow = nums[0];
            int fast = nums[nums[0]];
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            slow = 0;
            while (slow != fast) {
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
        return -1;
    }
}

JavaScript实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    const len = nums.length;
    if (len > 0) {
        let slow = nums[0];
        let fast = nums[nums[0]];
        while (slow !== fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        slow = 0;
        while (slow !== fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
    return -1;
};