【原】627，二分法解寻找重复数

问题描述

来源：LeetCode第287题

难度：中等

给定一个包含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中只有一个整数出现两次或多次，其余整数均只出现一次

二分法解决

找出重复数字，这题有两个限制条件，一个就是不能修改原数组，一个是使用O（1）的额外空间。有了这两个限制条件，那么通过排序再查找这种方式是行不通了。

这题我们可以使用二分法进行查找，一般使用二分法的时候数组必须是有序的，但这题数组是无序，不过没关系。这里使用二分法的两个指针指向的不是数组中的元素，而是一个有序的区间。使用二分法之前我们首先要搞懂什么是抽屉原理。

桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。

对于这道题我们使用两个指针，一个指向最小值1，一个指向最大值nums.length-1，每次我们取这两个指针的中间值mid，然后统计数组中小于等于mid元素的个数count。

如果count大于mid，根据抽屉原理，重复数字肯定小于等于mid，我们缩小两指针的范围。举个例子：比如小于等于5的个数是6，也就是说6个苹果放到5个抽屉中，那么至少有一个抽屉不少于两个苹果。

如果count不大于mid，那么重复数字肯定是大于mid的。这种情况下是不适合抽屉原理的，比如把3个苹果放到5个抽屉中，也有可能某个抽屉的苹果数不少于两个。但这题说了是n+1个元素，只有一个是重复的，也就是说前面3个苹果放到5个抽屉中不可能某个抽屉的苹果数大于1。这里以示例一为例来画个图看一下

--------------------------------------------

--------------------------------------------

来看下代码

public int findDuplicate(int[] nums) {
    int left = 1;
    int right = nums.length - 1;
    while (left < right) {
        int mid = (right + left) >> 1;
        //统计小于等于mid的数量
        int count = 0;
        for (int num : nums) {
            if (num <= mid)
                ++count;
        }
        if (count > mid)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

●624，给表达式添加运算符（回溯算法解决）

●607，位运算等多种方式判断是否存在重复元素

●449，快慢指针解决环形链表

●460. 快慢指针解环形链表 II