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