寻找重复数

寻找重复数

解题思路

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

    由于所有的数字都是1-n之间，而且只存在一个重复数字，如果没有重复数，

那么刚好就是n个数字，mid = (0+n-1)/2，遍历一遍数组，计算小于等于mid的值的个数，
如果没有重复数，小于等于mid的数字刚好是mid个(1,2,...mid)，如果个数大于mid，说明在（1，mid）之间，存在重复的数字；反之，如果个数小于等于mid，说明（mid+1,n）之间，
存在重复的数字；

示例 1:

    arr = [1,3,4,2,2] 
    mid = (0 + 4) / 2 = 2 arr小于等于的2有3个（1，2，2），所以小于mid（2）的1-2中，肯定有重复的值，
   high = mid=2，low = 0
    mid = (0 + 2) / 2 = 1 arr小于等于的1有1个(1)，2到2中肯定有重复的值
   low=mid+1=2，hight=2，不满足while条件，所以这个重复值就是2
    
    所以重复的数是 2 

代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low  = 0;
        int high = nums.size() -1;
        while(low < high)
        {
            int mid = (low+high) / 2;
            int count = 0;
            for(size_t i=0;i<nums.size();i++)
            {
                if(nums[i] <= mid)
                {
                    count += 1;
                }
            }

            if(count <= mid)
                low = mid+1;
            else
                high = mid;
        }
        return low; 
    }
};