题目描述
找出数组中重复的数字
样例
1,2,3,4,4,5,6
返回4
算法1
(计数法) $O(n)$
用一个数组counter来记录每个数字出现的次数
在统计过程中 如果 nums[i]<0||nums[i]>=len
即某个数 <0或者 >n-1 时就返回 -1
第一个出现次数>1的数就是结果
counter[i]>1 时 返回 i 即当前遍历到的数即可
时间复杂度 O(n)
参考文献
Java 代码
class Solution {
public int duplicateInArray(int[] nums) {
if(nums==null || nums.length==0){
return -1;
}
int len = nums.length;
int[] counter = new int[len];
for(int i=0;i<len;i++){
if(nums[i]<0||nums[i]>=len){
return -1;
}else{
counter[nums[i]]++;
}
}
for(int i=0;i<len;i++){
if(counter[i]>1){
return i;
}
}
return -1;
}
}