287-寻找重复数(Find the Duplicate Number)

原文链接: https://leetcode-cn.com/problems/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 uses 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 = [1,1]
Output: 1

Example 4:

Input: nums = [1,1,2]
Output: 1

Constraints:

1 <= n <= 10⁵
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) 的额外空间。

示例 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

提示：

1 <= n <= 10⁵
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

通过代码

高赞题解

解题思路：

题目要求查找重复的整数，很容易想到使用「哈希表」，但是题目中要求：「你设计的解决方案必须不修改数组 nums 且只用常量级 $O(1)$ 的额外空间」，因此使用「哈希表」不满足题目的要求；
但是题目中还说：「数字都在 $1$ 到 $n$ 之间（包括 $1$ 和 $n$）」，因此可以使用「二分查找」。

可以使用「二分查找」的原因

因为题目要找的是一个整数，并且这个整数有明确的范围，所以可以使用「二分查找」。

重点理解：这个问题使用「二分查找」是在数组 [1, 2,.., n] 中查找一个整数，而 并非在输入数组数组中查找一个整数。

使用「二分查找」查找一个整数，这是「二分查找」的典型应用，经常被称为「二分答案」。在题解中，「题型二」与「题型三」都是这样的问题。

事实上，「幸运 52 」猜价格游戏，就是「二分答案」。玩家猜一个数字，如果猜中，游戏结束，如果主持人说「猜高了」，应该猜一个更低的价格，如果主持人说「猜低了」，应该猜一个更高的价格。

继续 解题思路：

每一次猜一个数，然后 遍历整个输入数组，进而缩小搜索区间，最后确定重复的是哪个数。

理解题意：

n + 1 个整数，放在长度为 n 的数组里，根据「抽屉原理」，至少会有 1 个整数是重复的；

抽屉原理：把 10 个苹果放进 9 个抽屉，一定存在某个抽屉放至少 2 个苹果。

思路分析：

找重复，最容易想到的办法是使用「哈希表」；
但是题目要求：设计的解决方案必须不修改数组 nums 且只用常量级 $O(1)$ 的额外空间；
查找一个有范围的整数可以使用「二分查找」；
「快慢指针」的做法请见其它题解。

方法：二分查找

二分查找的思路是先猜一个数（有效范围 [left..right] 里位于中间的数 mid），然后统计原始数组中 小于等于 mid 的元素的个数 cnt：

如果 cnt 严格大于 mid。根据抽屉原理，重复元素就在区间 [left..mid] 里；
否则，重复元素就在区间 [mid + 1..right] 里。

与绝大多数使用二分查找问题不同的是，这道题正着思考是容易的，即：思考哪边区间存在重复数是容易的，因为有抽屉原理做保证。

参考代码：

[]
public class Solution {

    public int findDuplicate(int[] nums) {
        int len = nums.length;
        int left = 1;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            int cnt = 0;
            for (int num : nums) {
                if (num <= mid) {
                    cnt += 1;
                }
            }

            // 根据抽屉原理，小于等于 4 的个数如果严格大于 4 个，此时重复元素一定出现在 [1..4] 区间里
            if (cnt > mid) {
                // 重复元素位于区间 [left..mid]
                right = mid;
            } else {
                // if 分析正确了以后，else 搜索的区间就是 if 的反面区间 [mid + 1..right]
                left = mid + 1;
            }
        }
        return left;
    }
}

解释：

题目中说：长度为 n + 1 的数组，数值在 1 到 n 之间。因此长度为 len，数值在 1 到 len - 1 之间；
使用 while (left < right) 与 right = mid; 和 left = mid + 1; 配对的写法是为了保证退出循环以后 left 与 right 重合，left （或者 right）就是我们要找的重复的整数；
在 循环体内，先猜一个数 mid，然后遍历「输入数组」，统计小于等于 mid 的元素个数 cnt，如果 cnt > mid 说明重复元素一定出现在 [left..mid] 因此设置 right = mid；

如果觉得上面这句话比较绕的话，可以用一个具体的例子来理解：如果遍历一遍输入数组，统计小于等于 $4$ 的元素的个数，如果小于等于 $4$ 的元素的个数严格大于 $4$ ，说明重复的元素一定出现在整数区间 [1..4]，依然是利用了「抽屉原理」。注意这里加着重号的地方。

复杂度分析：

时间复杂度：$O(N \log N)$，二分法的时间复杂度为 $O(\log N)$，在二分法的内部，执行了一次 for 循环，时间复杂度为 $O(N)$，故时间复杂度为 $O(N \log N)$。
空间复杂度：$O(1)$，使用了一个 cnt 变量，因此空间复杂度为 $O(1)$。

补充：

但本题的场景和限制是极其特殊的，实际工作中和绝大多数算法问题都不会用「时间换空间」；
关于如何使用「二分查找」做对「力扣」上所有的问题，可以看第 35 题的题解；
这题二分查找和快慢指针都不是常规思路，面试的时候最好提一下：因为有各种限制，才用二分这种耗时的做法，用快慢指针是因为做过类似的问题。

统计信息

通过次数	提交次数	AC比率
190669	290666	65.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
缺失的第一个正数	困难
只出现一次的数字	简单
环形链表 II	中等
丢失的数字	简单
错误的集合	简单

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途