|
锁定老帖子 主题：水木上看到的一个面试题,讨论很激烈
该帖已经被评为新手帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-05-20
yangmen066 写道 AppleRipe 写道 遍历，比较，设置一个临时变量保存最大的数或最小的数，遍历完后最大的数加1或最小的数减1都可以满足条件，内存不考虑jvm自身，几个字节应该够了吧
感觉靠谱 这个还是靠谱的 不过有一个小bug 如果这40亿个数中包含最大，最小数怎么办呢？ |
| 返回顶楼 | |
|
发表时间：2011-05-20
yangmen066 写道 AppleRipe 写道 遍历，比较，设置一个临时变量保存最大的数或最小的数，遍历完后最大的数加1或最小的数减1都可以满足条件，内存不考虑jvm自身，几个字节应该够了吧
感觉靠谱 结果恰好，最大数，最小数都在文件里了 |
| 返回顶楼 | |
|
发表时间：2011-05-20
最后修改：2011-05-20
个人决定这题可以用字典树进行存储，这样查找的时间复杂度是数字本身的长度。
|
| 返回顶楼 | |
|
发表时间：2011-05-20
yangmen066 写道 AppleRipe 写道 遍历，比较，设置一个临时变量保存最大的数或最小的数，遍历完后最大的数加1或最小的数减1都可以满足条件，内存不考虑jvm自身，几个字节应该够了吧
感觉靠谱 如果得到的最大或最小的就是整数溢出的那个限界值，+1或-1不是溢出了么 |
| 返回顶楼 | |
|
发表时间：2011-05-20
最后修改：2011-05-20
yangmen066 写道 AppleRipe 写道 遍历，比较，设置一个临时变量保存最大的数或最小的数，遍历完后最大的数加1或最小的数减1都可以满足条件，内存不考虑jvm自身，几个字节应该够了吧
感觉靠谱 感觉不靠谱，万一最大值是整数的最大值，最小值是整数的最小值呢？岂不溢出了 
呀，楼上有人回复了 
|
| 返回顶楼 | |
|
发表时间：2011-05-20
doylecnn 写道 去看《编程珠玑》去
就是书里的例子，照搬不动 思路是2分 这题目说是读取一遍，2分法那个不是每次都要根据位不同分成2个不同文件，然后再读取少整数的那文件的整数么，这样不止读一遍了吧 |
| 返回顶楼 | |
|
发表时间：2011-05-20
二分法好像得实现排好序吧。新鸟，不懂，根据自己理解说的。
|
| 返回顶楼 | |
|
发表时间：2011-05-20
应该使用位操作，找到32位未出现过的组合，即是未出现过的整数
|
| 返回顶楼 | |
|
发表时间：2011-05-20
典型的位图排序
|
| 返回顶楼 | |
|
发表时间：2011-05-20
10M内存可以放 2.5M个数, 产生2.5M个随机数, 然后遍历文件, 大约就有一个数不在文件中
|
| 返回顶楼 | |
