锁定老帖子 主题:一道算法面试题
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-09-30
声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2011-09-30
想到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); } |
|
返回顶楼 | |
发表时间:2011-09-30
申请一亿位的数组空间,全部置0,然后以随机数为数组索引,将该位置1,遍历数组,输出位不为1的索引
|
|
返回顶楼 | |
发表时间:2011-09-30
evil9999 写道 申请一亿位的数组空间,全部置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速度够快 算法成了浮云 |
|
返回顶楼 | |
发表时间:2011-09-30
yangelhun 写道 evil9999 写道 申请一亿位的数组空间,全部置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来计算的,这个可以减少空间的利用率。楼主可以试验一下吧 |
|
返回顶楼 | |
发表时间:2011-09-30
百度的面试题目~~~~, 用2bit*1亿 的内存就可以解出来, 00 表示没有使用,01表示这个位置有这个数字 。找出这些00位置的就是答案。
这样性能很高~~~~ |
|
返回顶楼 | |
发表时间:2011-09-30
nC公司才出玩算法题目~~~
|
|
返回顶楼 | |
发表时间:2011-09-30
最后修改:2011-10-01
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 |
|
返回顶楼 | |
发表时间:2011-09-30
既然都叫算法题,还有人鄙视算法。真晕
不过这个题目也太BT了,9分之一都是空的,悲剧啊 |
|
返回顶楼 | |
发表时间:2011-09-30
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 为所需结果 } } |
|
返回顶楼 | |