一道数组面试题求助

Question

给定一个整形数组 int[] a = {1,9,5,7,,2,4,1,6,1,33,45}  返回1；即找出a中重复的数并返回，a中只有一个数字重复 不能先排序再查找  写出时间空间复杂度都较理想的算法：我当时想了三种方法最后想到用set的去重功能来解决 但面试官说复杂度较高 但set的方法比较接近答案了，回来后还是想不出一种很精巧的算法  发帖求助大神

Answer 1

如果数组a中的数字，大小相对可控，比如都 < 一万，那么还可以直接用数组来解决，无非是浪费空间；就算用BitArray，也就节省1个数量级的空间。如果数字取值是 正负2亿的话，应该没啥比hash更优的算法了。

Answer 2

set复杂度很高么？不也就O(N)么。

Answer 3

内部的复杂度高，毕竟是树，也就是存在log2n了

Answer 4

不计空间么,int最大为4G
直接用掉4G bit做标记更快O(N)

Answer 5

用数组元素作为键，存HASHMAP怎么样？

Answer 6

这个不需考虑集合的，用一下算法，复杂度为О(n²)：
public static int search(int[] a) {
        if (a != null && a.length > 0) {
            int len = a.length;
            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    if (a[i] == a[j])
                        return a[j];
                }
            }
        }
        return Integer.MAX_VALUE;
    }

Answer 7

如果数字的大小有限制，如最大为100
可以创建一个大小为100的数组，初始化所有的值为一个不可能的数，例如－1，然后把每个数放到对应的位置，如这个位置不为0，则说明这个数是重复的
这是用了hash的特点面试的时候，要尽量的问面试官各种条件，很多东西面试官是不会直接告诉你的，需要你去主动的沟通

Answer 8

嗯 确实是这样 8楼真相了！！  貌似目前用hash来解决是比较理想的了