|
锁定老帖子 主题：水木上看到的一个面试题,讨论很激烈
该帖已经被评为新手帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-05-31
kangxdw 写道 其实我很想问一句，为什么没有人考虑用树来做。。。
lvl1:null lvl2:{1,2,3,4,5,6,7,8,9,0} lvl3:同上 lvln:同上 然后遍历，形成连接。 遍历完后，找到任意两点之间没有连接的。。。就是咯。 你们觉得呢？ 好方法！ |
| 返回顶楼 | |
|
发表时间：2011-05-31
sea0108 写道 kangxdw 写道 其实我很想问一句，为什么没有人考虑用树来做。。。
lvl1:null lvl2:{1,2,3,4,5,6,7,8,9,0} lvl3:同上 lvln:同上 然后遍历，形成连接。 遍历完后，找到任意两点之间没有连接的。。。就是咯。 你们觉得呢？ 好方法！ 你确定扫描一遍可以? |
| 返回顶楼 | |
|
发表时间：2011-05-31
喜羊羊与灰太狼 写道 nianien 写道 supertaxi 写道 扫描一遍后的结果呢...不得放在内存中啊
我觉得给指定内存是用来迷惑人的,几个字节的内存足矣 那你给说下你的想法吧，看看你用多少个字节，谢谢 几个字节确实可以，就看你一次读取多少来判断。 |
| 返回顶楼 | |
|
发表时间：2011-05-31
只需要循环一次，求和、求积，然后根据公式可以求得该数
|
| 返回顶楼 | |
|
发表时间：2011-06-01
最后修改：2011-06-01
哎， 布隆过滤器得了， 搞得这么复杂。 否则很难有解～
内存不够？ 开个10m mmap, 哈哈哈 要么使用haffman算法, 量化？ 不过我也没有想明白怎么建数据结构。 |
| 返回顶楼 | |
|
发表时间：2011-06-01
不就是要建立一棵键树吗？每个节点就是一个0-9的数字，第一层可以是个位，最后一层就是最高位，比如11层就可以表示100亿个各不相同数字了。
|
| 返回顶楼 | |
|
发表时间：2011-06-01
xielingjiang 写道 不就是要建立一棵键树吗？每个节点就是一个0-9的数字，第一层可以是个位，最后一层就是最高位，比如11层就可以表示100亿个各不相同数字了。
哥们儿，10M内存，放不下能表示40亿个整数的键树。 |
| 返回顶楼 | |
|
发表时间：2011-06-02
鄙视哪些不考虑内存、不考虑结构的同学。
一组数据，在内存一定的时候，如果用bitset都没办法表示，那其他结构更没有办法表达完了。 |
| 返回顶楼 | |
|
发表时间：2011-06-02
nianien 写道 sea0108 写道 kangxdw 写道 其实我很想问一句，为什么没有人考虑用树来做。。。
lvl1:null lvl2:{1,2,3,4,5,6,7,8,9,0} lvl3:同上 lvln:同上 然后遍历，形成连接。 遍历完后，找到任意两点之间没有连接的。。。就是咯。 你们觉得呢？ 好方法！ 你确定扫描一遍可以? 文件是扫描一片即可。后续的操作都是在内存里面对这个“树”进行操作。 |
| 返回顶楼 | |
|
发表时间：2011-06-02
最后修改：2011-06-02
lnaigg 写道 能用文件，那这题还有难度么。 你去看看BitSet的实现再看看我这个解决思路， 我只是把BitSet简化并且使用文件保存而已。 对了，你知道什么是BitSet或者布隆过滤吗， 布隆过滤和BitSet有什么联系？ 这些经典的算法和结构都不能用10M内存解决这个问题， 如果你能用10M内存不用文件解决，我立马膜拜之！ 不要啥也不明白就像傻帽样出来丢 |
| 返回顶楼 | |
