一道数组面试题求助
给定一个整形数组 int[] a = {1,9,5,7,,2,4,1,6,1,33,45} 返回1；

即找出a中重复的数并返回，a中只有一个数字重复 不能先排序再查找  

写出时间空间复杂度都较理想的算法：

我当时想了三种方法最后想到用set的去重功能来解决 但面试官说复杂度较高 但set的方法比较接近答案了，回来后还是想不出一种很精巧的算法 发帖求助大神

------解决方案--------------------
如果数组a中的数字，大小相对可控，比如都 < 一万，那么还可以直接用数组来解决，无非是浪费空间；就算用BitArray，也就节省1个数量级的空间。

如果数字取值是 正负2亿的话，应该没啥比hash更优的算法了。
------解决方案--------------------
如果数字的大小有限制，如最大为100
可以创建一个大小为100的数组，初始化所有的值为一个不可能的数，例如－1，然后把每个数放到对应的位置，如这个位置不为0，则说明这个数是重复的
这是用了hash的特点

面试的时候，要尽量的问面试官各种条件，很多东西面试官是不会直接告诉你的，需要你去主动的沟通