系列文章：

一 摘要

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

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

二 题目描述

引用的描述原文如下：

给定一个包含 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;
}