一路牛逼的java面试题

一道牛逼的java面试题
一个数组长度是10万 存的是数字而且无序 其中有两个相同的数字 用最优算法求出这两个数来
例如arr[0..100000] 其中arr[0]和arr[22]相同

[解决办法]
第一时间想到的是用HashSet来搞，运气好的话，不需要遍历整个数组，就可以退出循环了。
HashSet<Integer> set = new HashSet<Integer>();
for (a in arr) {
if (set.contains(a)) break; // 找到啦
set.add(a);
}
[解决办法]

Java code

//时间和空间,看要那个了    public static void main(String[] args) {        // TODO code application logic here        int data[] = new int[100000];        for (int i = 0; i < data.length; i++) {            data[i] = i + 1;        }        data[22] = data[0];        try {            System.out.println(sf(data));        } catch (Exception ex) {            Logger.getLogger(Test.class.getName()).log(Level.SEVERE, null, ex);        }    }    static int[] key = new int[]{0b1, 0b10, 0b100, 0b1000, 0b10000, 0b100000, 0b1000000, 0b10000000};    static int sf(int data[]) throws Exception {        int len = 256 * 1024 * 1024;        //分页,正和负各2g bit,共要4gbit/8=512gbyte        byte[] p1 = new byte[len];        byte[] p2 = new byte[len];        int index;        for (int d : data) {            index = d & 0x7fff;            if (d < 0) {                if ((p2[index / 8] & key[index % 8]) > 0x0) {                    return index;                } else {                    p2[index / 8] |= key[index % 8];                }            } else {                if ((p1[index / 8] & key[index % 8]) > 0x0) {                    return index;                } else {                    p1[index / 8] |= key[index % 8];                }            }        }        throw new Exception();    }
[解决办法]
探讨


第一时间想到的是用HashSet来搞，运气好的话，不需要遍历整个数组，就可以退出循环了。
HashSet<Integer> set = new HashSet<Integer>();
for (a in arr) {
  if (set.contains(a)) break; // 找到啦
  set.add(a);
}

[解决办法]
这个简单，源码送上

Java code
package com.comtop.test;import java.util.HashMap;import java.util.Map;/** * * @author  czm * @since   JDK1.5 * @history 2012-2-29 czm 新建 */public class BigDataRepeatTest {    private static final int[] data = new int[100000];    public static void main(String[] args) {        //初始化data        for(int i = 0;i<data.length;i++){            data[i] = i;        }        data[99999] = 0;        long startTime = System.currentTimeMillis();        Map<Integer,Integer> map = new HashMap<Integer,Integer>();        for(int i = 0;i<data.length;i++){            if(map.get(data[i])!=null){                System.out.println("第"+i+"个重复，重复值为"+data[i]);                System.out.println("get you:"+data[i]);                break;            }else{                map.put(data[i], data[i]);            }        }        long endTime = System.currentTimeMillis();        System.out.println("查找"+data.length+"重复数据一共耗费："+(endTime-startTime)+"毫秒");    }}