633. 寻找重复的数关注问题
描述
给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
1.不能修改数组(假设数组只能读)
2.只能用额外的O(1)的空间
3.时间复杂度小于O(n^2)
4.数组中只有一个重复的数，但可能重复超过一次
您在真实的面试中是否遇到过这个题？ 是
题目纠错
样例
样例 1:
输入:
[5,5,4,3,2,1]
输出:
5
样例 2:
输入:
[5,4,4,3,2,1]
输出:
4
思路：限制实在太多了有木有，考虑到空间约束，貌似我们只能一个数一个数地试，但是又要求小于O(n^2)的复杂度，甚至都逼得孩子想到了随机大法(雾)。等等，一个个试？一个个试实在太慢了，有没有办法？自然可以联想到二分答案的做法，那么这题可以二分答案吗，我们试试。
假设我们当前在试x是否是重复的数，由于一共有n+1个数，而每个数都是处于[1,n]的，那么重复的数必定至少出现了两次，假设重复的数为y，并且满足y<=x，那么处于[x+1,n]的数最多只会出现一次，即>x的数的个数一定满足<=n-x，而一共有n+1个数，也就是说，设一共有z个数满足<=x，那么z>=(n+1)-(n-x)=x+1。
换言之，如果<=x的数的个数>=x+1，则重复的数一定处在[1,x]之中，否则处在[x+1,n]。
class Solution {
public:/*** @param nums: an array containing n + 1 integers which is between 1 and n* @return: the duplicate one*///二分法 因为总共有n+1个数 且只有一个数重复 所以如果后面无重复 最多只有 n-mid个数 那么前面会剩下 mid+1 个数 必有重复int check(vector<int> &nums,int n,int num){// 统计小于等于num的个数int i,c=0;for(i=0;i<n;++i){if(nums[i]<=num)++c;}return c;}int findDuplicate(vector<int> &nums) {// write your code hereint i,n=nums.size(),Mid,L=1,R=n-1;while(L<R){Mid=(L+R)>>1;if(check(nums,n,Mid)<=Mid){L=Mid+1;}else R=Mid;}return R;}
};