系列文章：

算法题目解析：从一道题目看动态规划

Leetcode 题目解析：274. H 指数

Leetcode 题目解析：279. 完全平方数

一 摘要

基于数组的运算，是面试算法题中很大的一部分题目。很多问题的输入，都可以以数组的形式给出，所以，我们对数组特性、常见题目的掌握程度，就直接决定了我们对相关算法的解决能力。

遍历、排序、二分...这些都是在解决具体问题时常用的手段；作为辅助，也可能有双指针、数组作为循环队列等场景。本篇要解析的这道重复数字寻找，也是其中一个典型的题目。

二 题目描述

引用leetcode的描述原文如下：

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

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

三 题目解析

3.1 示例

输入：nums = [1,3,4,2,2]输出：2

3.2 解析

3.2.1 排序与哈希

判断一个数字是否重复并不难，比较容易想到的就是排序和哈希；分别利用数字的大小，和 map 存储并判断 contains()方法值的真假来确定是否有重复。但这道题要求不修改数组，并且只用常量级 O(1)的额外空间，也就是说，空间复杂度必须是 O(1)，那么哈希的方法就不符合了。

再看排序，基于比较排序，只用一个临时变量来实现数字的位置交换，是可行的；再得到排序结果之后，我们再比较相邻的两个数字看是否相同；那么这种方法最好的时间复杂度是 O(nlogn)。那么是否有更好的办法呢？

3.2.2 二分

排序的目的是想通过相邻数字比较来判断是否重复，但实际上，我们并不需要对所有数字进行排序。考虑到 top n 元素的查找方法，是否可以也利用二分法来实现呢？

数组本身无序，所以我们不能直接对数组 nums 本身进行二分；但我们可以对坐标数组{0,1,2,...,n-1}进行二分搜索。当然，对比的不是元素本身，而是小于或等于某个数字的元素个数。

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

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

否则，重复元素就在区间 [mid + 1..right] 里。

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

3.2.3 代码

public int findDuplicate(int[] nums) {    int n = nums.length;    int l = 1, r = n - 1, ans = -1;    while (l <= r) {        int mid = (l + r) >> 1;        int cnt = 0;        for (int i = 0; i < n; ++i) {            if (nums[i] <= mid) {                cnt++;            }        }        if (cnt <= mid) {            l = mid + 1;        } else {            r = mid - 1;            ans = mid;        }    }    return ans;}