【hot100-java】【寻找重复数】
技巧
使用字典，边记录边比较，有直接输出。
def findDuplicate(nums):
seen = {}
for num in nums:
if num in seen:
return num
seen[num] = True
return None可惜不是O(1)
二分查找
class Solution {
public int findDuplicate(int[] nums) {
int left=0;
int right=nums.length-1;
while(left<right){
int mid=(left+right)/2;
int count=0;
for (int num:nums){
if(num<=mid){
count++;
}
}
if(count<=mid){
left=mid+1;
}
else{
right=mid;
}
}
return left;
}
} 