从品牌网站建设到网络营销策划,从策略到执行的一站式服务
nums
包含 n + 1
个整数,每个整数是从 1
到 n
(包括边界),保证至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
1.不能修改数组(假设数组只能读)
2.只能用额外的O(1)的空间
3.时间复杂度小于O(n^2)
4.数组中只有一个重复的数,但可能重复超过一次
给出 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的值就是所求
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图