633.寻找重复的数-创新互联

给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

 注意事项

1.不能修改数组(假设数组只能读)
2.只能用额外的O(1)的空间
3.时间复杂度小于O(n^2)
4.数组中只有一个重复的数，但可能重复超过一次

创新互联是专业的川汇网站建设公司，川汇接单;提供成都网站制作、网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行川汇网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!   样例

给出 nums = [5,5,4,3,2,1]，返回 5.
给出 nums = [5,4,4,3,2,1]，返回 4.

 1   int findDuplicate(vector &nums) {
 2 // write your code here 3 int left=1,right=nums.size()-1;
 4 int mid=left+(right-left)/2;
 5 int left_num;
 6 while(left

自己没想出来，照着网上的思路写了一个

left是1，right是n。mid算出来以后遍历数组，看有多少小于等于它的，如果统计的数量小于等于mid这个数的本身，就说明重复的数在比mid大的那边。

于是就left＝mid＋1（因为不够嘛所以不要了）或者right＝mid。最后left＝right的值就是所求


本文名称：633.寻找重复的数-创新互联
URL地址：http://bjjierui.cn/article/cdhcds.html