今日题目链接:数组中重复的数字
数组中重复的数字
难度：简单
描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
数据范围
数据范围：0 0≤n≤10000
进阶：时间复杂度O(n) ，空间复杂度O(n)
举例
解题思路
方法一：利用HashMap来记录每个数字出现的次数，key为数组中的数字，value为出现的次数，遍历一遍数组，每次利用ContainsKey的true或者false来进行判断，如果为true说明map中已经存在这样的数字了，便将其value 1；如果为false说明是第一次出现这样的数字直接将其put进map中value为1
方法二：数据重排，重头到尾扫描数组S中的每一个元素，当扫描到第i个元素的时候，比较第i个元素位置的值m是否等于i，如果相等，则说明该元素已经在排好序的位置，继续扫描其他元素；如果不相等，先判断m是否等于S[m]，相等则说明不同位置上的元素值相等，即元素重复。直接返回元素；否则交换m和S[m]将他们放置到排好序的位置
实现代码（java）
方法一：
代码语言：javascript复制import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @return int整型
*/
public int duplicate (int[] numbers) {
// write code here
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 0; i < numbers.length;i ){
if(map.containsKey(numbers[i])){//如果为true，则将value 1
map.replace(numbers[i],map.get(numbers[i]),map.get(numbers[i]) 1);
}else{//为false，则将value设为1
map.put(numbers[i],1);
}
}
//遍历一遍map，如果value不为1直接return出去，如果都没有直接return -1
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(entry.getValue()!=1){
return entry.getKey();
}
}
return -1;
}
}方法二:
代码语言：javascript复制int duplicate(vector<int>& numbers) {
int i=0,n=numbers.size();
while(i<n){
if(numbers[i] == i){ //第i个位置的元素就是i
i ;
continue;
}else{
if(numbers[i] == numbers[numbers[i]]) //不同位置上出现了相同的元素，即元素重复
return numbers[i];
else
swap(numbers[i],numbers[numbers[i]]); //交换元素到对应的位置
}
}
return -1;
}
