频道栏目
首页 > 考试 > 其他 > 正文

Find the Duplicate Number(二分和List)

2018-06-28 14:08:28         来源:heiyiming123的博客  
收藏   我要投稿

题意:找出数组中的重复元素。

思路1:将数组中的元素放入List里面,当有元素已经存在时就直接返回这个值。

代码:

class Solution {
public int findDuplicate(int[] nums) {
List res =new ArrayList();
int result=0;
for(int i=0;i if(!res.contains(nums[i])){
res.add(nums[i]);
}
else{
result=nums[i];
break;
}
}
return result;
}

}

思路二:二分法。找到中间大小的数。计数比中间数小的个数,若这个个数大于数组长度的一般,说明重复数在前半部分,否则在后半部分。然后对应改变查询首尾的值即可。

class Solution {
public int findDuplicate(int[] nums) {
int left=1;
int right=nums.length-1;
int middle;
while(right>left){
int num=0;
middle=(right+left)/2;
for(int i=0;i if(middle>=nums[i]){
num++;
}
}
if(num>middle){
right=middle;
}
else
left=middle+1;
}
return left;
}
}

上一篇:二进制中1的个数问题解析
下一篇:Climbing Stairs 爬楼梯问题解析
相关文章
图文推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站