寻找重复数-LeetCode287

一、题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

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

示例一：

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

二、解题思路（这道题的解题思路很难想到，以前做的题从来没有碰到过。）

（1）题目有明确要求：设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。这就告诉我们，不能对nums数组进行排序，不能使用额外的辅助数组，所以我们就只能对原数组进行遍历（没限制时间复杂度），在遍历的过程中找到原问题的解

（2）利用二分查找法。

1）二分查找需要确定区间的左右端点，且能有某个性质，能在区间对半分后舍弃调其中一半的区间，在该题中，因为我们知道给定的数组中所有数的一个范围，也就是nums.length-1，利用这个性质，我们可以设置初始区间左右端点如下：

left=1 //表示所有数的最小

right=nums.length-1 //所有数的最大

所以该题中找的mid与普通二分法不同，该题中所找的mid就是所给数的范围的中间，而不用再取nums[mid]来在题中进行判断

2） 那么我们来怎么判断哪个区间该舍弃？哪个区间该留下呢？

我们定义 cnt[i] 表示nums 数组中小于等于i 的数有多少个，假设我们重复的数是 target，那么 [1,target−1]里的所有数满足 cnt[i]≤i，[target,n] 里的所有数满足 cnt[i]>i，具有单调性。以此就可以得知应舍弃掉哪个区间。例：

nums[i]={1,2,2,2,5,3}，区间范围为[1,5](nums[i]共有6个数)

i	1	2	3	4	5
nums[i]	1	4	5	5	6

此题中target=2

[1,2)：cnt[1]<=1

[2,5]：cnt[2]=4>=2,cnt[3]=5>=3,cnt[4]=5>=4;cnt[5]=6>=5

结论成立

三、代码示例

/**
* 该题涉及nums数组中数的范围，是一个突破口
 * 二分查找应用题型：target左边范围的数和右边范围的数有明显区别，且以target为界限划分的小区间也具有前面的性质
*/

//以重复的数target为界：小于target的数的数量<=i;大于等于target的数的数量>i
class Solution51 {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        //l、r指针是指向的nums的范围，而不是nums中的数的下标
        //如：nums={1,3,2,2,2,5}：其范围是1,2,3,4,5，而l指向1，r指向5，所以mid为3
        int l = 1, r = n - 1, ans = -1;
        //为什么循环条件为：l<=r？以重复的数target为界：小于target的数的数量<=i;大于等于target的数的数量>i，
        //所以任何时候确定l、r进而确定的区间必定是向target靠拢的，直至l>r
        while (l <= r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= mid) {
                    cnt++;
                }
            }
            //如果当前小于中间的数的数量比中间的数小，说明重复的数是比中间的数大的，且重复的数可能占用了[1,mid]中的数的位置
            if (cnt <= mid) {
                l = mid + 1;
            } else {
                //如果当前大于中间的数的数量比中间的数大，说明重复的数是比中间的数小的
                r = mid - 1;
                ans = mid;
            }
        }
        return ans;
    }
}