leetcode287. 寻找重复数/二分法

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

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-duplicate-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思想

将数组排序，遍历数组，出现相邻两个数相等的，说明是重复数
不符合题意！！！改变了原数组

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 1; i < nums.size(); ++i){
            if(nums[i] == nums[i - 1])
                return nums[i];
        }
        return -1;
    }
};

二分法：
二分法是基于：数组中的数范围是确定的，并且，给定一个数k，如果小于等于k的数的个数是大于k的，那么说明重复的数一定在[left,k]中。
对于一个数k而言，如果[left,k]中没有重复元素的话，小于等于该元素的个数最多有k个，如果多余k个说明一定存在重复元素。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size() - 1;
        int l = 1, r = n;
        while(l < r){
            int mid = (l + r) >> 1;
            int cnt = 0;
            for(int i = 0; i <= n; ++i){
                if(nums[i] <= mid)
                    ++cnt;
            }
            if(cnt > mid){
                r = mid;
            }
            else
                l = mid + 1;
        }
        return l;
    }
};