一道算法面试题

面试题目的要求如下：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。当然，这个题目用笨拙的方法也是可以求出来的，有没有高效的方法呢？请大家赐教！

想到2种办法：
1、允许几率小的错判可以用布隆过滤器
2、用hash映射，直接将随机数映射到一亿那个数组里面。
   用hashmap的话代码如下，最后mmap中的value!=null的所有数据就是。

public static void main(String[] args) {
		int count = 100;
		Map map = new HashMap(count);
		for (int i = 1; i <= count; i++) {
			map.put(i, i);
		}
		Random ran = new Random();
		for (int i = 0; i < count / 10; i++) {
			int n = ran.nextInt(count);
			map.put(n, null);
		}
		System.out.println(map);
	}

申请一亿位的数组空间，全部置0，然后以随机数为数组索引，将该位置1，遍历数组，输出位不为1的索引

一亿位的数组空间占用空间97.6M

            public static void main(String args[]){
		long sT=System.currentTimeMillis();
		int[] x=new int[100000000];
		for(int i=0;i<10000000;i++){
			x[i]=5;
		}
		System.out.println( System.currentTimeMillis()-sT  );
		
	}

208ms搞定
如果内存够大cpu速度够快 算法成了浮云

不需要布隆，布隆是针对字符文本的。
1.可以用java的bitset，这个就是占用空间。1亿/32/1024/1024*32=95M

2.可以用bitmap这个，通过hashmap里放bitset来计算的，这个可以减少空间的利用率。楼主可以试验一下吧

百度的面试题目~~~~， 用2bit*1亿 的内存就可以解出来，   00  表示没有使用,01表示这个位置有这个数字 。找出这些00位置的就是答案。

这样性能很高~~~~

nC公司才出玩算法题目~~~

public void test() throws IOException {
        int[] randomNums = new int[10000000];
        Random random = new Random();
        for (int i = 0, length = randomNums.length; i < length; i++) {
            randomNums[i] = random.nextInt(100000000);
        }
        long start = System.currentTimeMillis();
        boolean[] bitArray = new boolean[100000000];
        for (int i = 0, length = randomNums.length; i < length; i++) {
            bitArray[randomNums[i]] = true;
        }
        for (int i = 0, length = bitArray.length; i < length; i++) {
            if (bitArray[i]) {
                continue;
            }
            // System.out.println(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("Spend milliseconds: " + (end - start));
    }

 

把内存调大点，挺快的。

 

Spend milliseconds: 657

既然都叫算法题，还有人鄙视算法。真晕

不过这个题目也太BT了，9分之一都是空的，悲剧啊

BitSet bs  = new BitSet(1 0000 0000);//
//data[1000 0000 ]
for(int i=0;i<10000 0000;i++){
    bs.set(data[i],true);
}
for(int i=0;i<10000 0000 ;i++){
    if(!bs.get(i)){
          //  i 为所需结果
     }
}