「力扣」第 287 题：数组中的重复数字（中等）

• 题目链接：寻找重复数 (opens new window)；
• 题解链接：使用二分法查找一个有范围的整数（结合抽屉原理） (opens new window)。

题目描述

给定一个包含 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 <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

题意分析

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

不是「有序数组」，但可以使用「二分查找」的原因：

• 因为题目要找的是一个 整数，并且这个整数有明确的范围，所以可以使用「二分查找」；
• 重点理解：这个问题使用「二分查找」是在数组 [1, 2,.., n] 中查找一个整数，而 并非在输入数组数组中查找一个整数。

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

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

解题思路

• 每一次猜一个数，然后 遍历整个输入数组，进而缩小搜索区间，最后确定重复的是哪个数；
• 把 n + 1 个整数，放在长度为 n 的数组里，根据「抽屉原理」，至少会有 1 个整数是重复的。

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

• 二分查找的思路是先猜一个数（有效范围 [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。

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

复杂度分析：

• 时间复杂度：，二分法的时间复杂度为 ，在二分法的内部，执行了一次 for 循环，时间复杂度为 ，故时间复杂度为 。
• 空间复杂度：，使用了一个 cnt 变量，因此空间复杂度为 。

补充：

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

总结

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

---

作者：liweiwei1419 链接：https://suanfa8.com/binary-search/solutions-2/0287-find-the-duplicate-number 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。