[数据结构与算法]剑指Offer03. 数组中重复的数字

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

输入：[2,3,1,0,2,5,3]
返回值：2
说明：2或3都是对的 

方法一：哈希表
使用哈希表存放每个元素及其出现的次数，HashMap第一个类型为元素类型(本题元素类型为Integer)，第二个类型为元素出现的次数，整数，Integer类型。首先遍历元素，统计每个元素出现的次数。然后再将哈希表的key以Set形式返回，遍历Set集合中的元素，对于每一个元素，使用get()方法获取其对应的value，即出现的次数。最后再根据题目要求，是返回出现一次、两次，还是任意次数的元素。

import java.util.*;
public class Solution {
    public int duplicate (int[] numbers) {
        // 使用HashMap，第一个Integer表示存放的数字，第二个Integer表示该数字出现的次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int count = map.getOrDefault(numbers[i], 0);
            map.put(numbers[i], count + 1);
        }
        for (Integer i : map.keySet()) {
            // 将map的key以Set形式返回
            int count = map.get(i);
            if (count > 1) {
                return i;
            }
        }
        return -1;
    }
}

时间复杂度：遍历元素，统计每个元素出现的次数，$O(n)$，之后再遍历哈希表的每个key，时间复杂度仍然是$O(n)$，两个过程是串行的，所以总的时间复杂度仍然是$O(n)$。空间复杂度：由于哈希表需要开辟空间，存放元素及其出现的次数，所以空间复杂度为$O(n)$。

总结：对于这种元素次数的问题，上面的哈希表代码可以当作模板，解决所有类似的问题，并且能做到不修改原数组，时间复杂度为$O(n)$是比较好的，唯一的不足是空间复杂度不是$O(1)$。剑指Offer 03中分为题目一和题目二，两个问题意思一样，只是题目二要求不能修改元素组，所以作者又给出了一种解法，但是用上面的哈希表的代码模板，两题一并AC。

结束语：如果本篇博客对您有帮助，请点赞、收藏或关注，您的鼓励是博主进步的动力，感谢支持，共同进步。