找数组中重复的数字（java代码实现）

描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1。

数据范围：0≤n≤10000

进阶：时间复杂度O(n)，空间复杂度O(n)

示例1

输入：[2,3,1,0,2,5,3]

返回值：2 说明：2或3都是对的

方法1：使用哈希表

思路：

既然是找重复的问题，那我们利用哈希表记录频率也是一样可以的。只要遇到的元素在哈希表中出现过，它就重复了。

具体做法：

step 1：遍历数组，将没有出现过的元素加入哈希表。 step 2：遇到的元素在哈希表中出现过就是重复数组。 step 3：遍历结束也没找到就返回-1.

具体代码实现：

public class Solution {
    public int duplicate (int[] numbers) {
        // write code here
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < numbers.length; i++){
            if(!map.containsKey(numbers[i])){
                map.put(numbers[i],1);
            }else{
                return numbers[i];
            }
        }
        return -1;
   }

方法2：使用Set集合，利用Set集合元素不重复的特性进行判断

思路：

一次遍历，遍历的时候添加元素，如果add返回为false，则此元素重复；

具体代码实现：

import java.util.*;
import java.util.HashSet; // 引入 HashSet 类

public class Solution {
     public int duplicate (int[] numbers) {
        // write code here
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < numbers.length; i++){
            if(!set.add(numbers[i])){
                return numbers[i];
            }
        }
        return -1;
   }
}