题目描述

给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思路

由于数组长度为n-1,而数的范围却是1到n,这里明显可以利用鸽巢原理.即一个萝卜一个坑,如果萝卜比坑多,则必有萝卜没有坑.

具体是通过对数组进行二分.在两个子数组中,一定存在某个子数组超过其所能容纳的数量(萝卜多而坑不够),此时只需要选择这种子数组,并不断对其进行二分,即可将范围缩小至一个点,这个点就是我们要求的重复数.[这道题要注意在一开始就划分好区间,这样在编写代码的时候就一目了然]

代码

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        auto len = nums.size();
        int low = 1, high = len - 1, mid;

        //[low, mid] + [mid + 1, high]
        while(low < high) {
            int less = 0;
            mid = low + (high - low) / 2;
            for(auto i : nums) {
                if(i >= low && i <= mid) less++;
            }
            if(less > mid - low + 1) high = mid;
            else low = mid + 1;
        }
        return low;
    }
};