首页 > 考试 > 其他 >

Find the Duplicate Number(二分和List)

2018-06-28

Find the Duplicate Number(二分和List)。找出数组中的重复元素。

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

思路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;
}
}

相关文章
最新文章
热点推荐