[数据结构与算法]力扣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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-duplicate-number

?方法一：二分查找

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

抽屉原理：把 10 个苹果放进 9 个抽屉，至少有一个抽屉里至少放 2 个苹果。

????????以数组1：[1, 3, 4, 2, 2] 为例：

????????我们定义 表示 ?数组中小于等于 ?的数有多少个，假设我们重复的数是 ，那么 里的所有数满足， 里的所有数满足，具有单调性。

以示例 1为例，我们列出每个数字的值：

????????示例中重复的整数是?，我们可以看到?中的数满足 ， 中的数满足 。由于?具有单调性，因此，可以对??数组进行二分查找。

? ? ? ? 又因为题意要求不能使用额外空间，所以代码中不能直接先求取??数组，需要在每次查找的过程中，动态计算当前的??值。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int len = nums.size();
        int l = 1, r = len - 1, ans = -1;
        while (l <= r) {
            // 右移一位  等同于 除2取整
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < len; ++i) {
                //cnt = cnt + (bool)(nums[i] <= mid)
                // 即 if(nums[i] <= mid) cnt++; else cnt+=0;
                cnt += nums[i] <= mid;
            }
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
};

注意：

题目中说：长度为 n + 1 的数组，数值在 1 到 n 之间。因此长度为 len = n + 1，n = len - 1，搜索范围在 1 到 len - 1 之间；代码中 l,?r 指的是nums的具体数值，而不是下标

使用二分查找的目标：是查找target使:

????????[1, target - 1]中的cnt都小于等于target, [target, n]中的cnt都大于target