有关数组的面试题，求思路，求答案。

Question

有一个数组，里面有10w个随机数，只有两个数字相同。
怎样找出这两个随机数，和下标位置？
要考虑最优性能

Answer 1

这10W个随机数应该有一个数值范围吧。
按照int来算的话，数值应该是1到100W。
那我就建立一个100W长度的数组，
读出来是哪个数？我就把这个数放到哪个位置的组里面，比如20，就放到int[20]里面。
最后查找一下哪个数组的长度为2就可以了。

Answer 2

以前去PPS面试，就问的一道这样类似的题吧。

Answer 3

随机数有范围没？如果范围不大，比如1-100w
声明个数组int[] array = int[1000000]
然后把整个数组扫描一遍，比如第i个元素值是Ai
就把array[Ai]++
扫描完了再遍历一次array看哪个元素值是2，它的下标就是重复的那个值呗

Answer 4

把这个数组里面的数字一个一个的放入一个set集合里面，每次放入一个判断set的size是否变大了，如果没变则找到了重复的元素，不知道想法可以否！

Answer 5

可以用Map来装  key为值  value为下标，一个for就能解决了

Answer 6

额，我能想到的也是循环放到set里。。

Answer 7

如果随机数有范围就用数组做，不然用set

Answer 8

揣测一下面试官的题意，他应该隐含以下两点：
1、100w个随机数并无范围，有可能出现的范围是负一亿----正一亿，甚至更大，一楼和三楼的方法有可能行不通；
2、注重考查你对集合API内部原理的理解，所以估计不允许你用Java集合API，4到7楼同学的方法均不是最优解答。
有以下两种建议的算法框架，分别对应HashMap和TreeSet的思想：
一、哈希表法：
1、由于数组长度是10w，根据“开根号原则”，不妨取余数为100，新建一个类class HashNode{
//数值域
 int value;
 //指针域，指向链表的下一个节点
 HashNode next;
         //对应大数组的下标
         int index;
}，开辟一个新的数组 HashNode[] array=new HashNode[100]，里边存放value为0~~99的100个链表头节点；
2、遍历10w的数组，依次对100取余，假设是203，对100取余为3，就用头插法插入array[3]对应的链表，并且采用“链表法”解决哈希冲突；
3、如果遇到既“哈希冲突”且"value相等"的情况，则说明遇到了重复值，程序结束。二、二叉树法：
由于TreeSet内部采用的“红黑树”，是非常难的一种数据结构，估计考不到这么深，有两种稍微简单的思路：
1、AVL树，性能接近红黑树，但要利用左左、右右、左右、右左四种旋转来维护平衡，也比较难；
2、普通的BST的插入算法，对于大量、乱序的随机数字，不会退化为链式结构，性能优良，且算法较为简便，参考《严蔚敏》的例题。