M********5
发帖数: 715 | 1 给你一个文件，包含很多个数，比如说1亿个数
产生一个数，是这1亿个数里面不存在的
但是你只有很小的内存，比如说100M
这个怎么实现 |
b********e
发帖数: 693 | 2 external sort first?
and then find a first not exist number by search sorted array
【在 M********5 的大作中提到】
: 给你一个文件，包含很多个数，比如说1亿个数
: 产生一个数，是这1亿个数里面不存在的
: 但是你只有很小的内存，比如说100M
: 这个怎么实现
|
i***1
发帖数: 95 | 3 bitvector, 参见programming pearls第一章
如果只是1亿个数字(0.1 Billion)的话，100M的内存，每个bit表示一个数字的话，就
够了。
如果是4Billion，不能fit进内存的话，就可以multi-pass. |
M********5
发帖数: 715 | 4 哦，明白了，谢谢各位了
刚刚翻了翻programming pearls，还确实有相似的题目 |
b********e
发帖数: 693 | 5 never read this book, sigh
【在 i***1 的大作中提到】
: bitvector, 参见programming pearls第一章
: 如果只是1亿个数字(0.1 Billion)的话，100M的内存，每个bit表示一个数字的话，就
: 够了。
: 如果是4Billion，不能fit进内存的话，就可以multi-pass.
|
w****c
发帖数: 2 | 6 找出一个最大的，加1不就行了？还有更简单地方法？还是我理解问题错了？ |
b********e
发帖数: 53 | 7 开始也这样想的，但是最大的可能就是int(or long)的最大值，再加1就溢出了 |
w****c
发帖数: 2 | 8 你这个确实是应该考虑的一点，但是面试的时候恐怕不是要考这点吧，我觉得。如果真
的面试官要这么追问一下，那可以用数组将最大数加一存起来吧，这样就不受int（
long）的限制了。而且这个问题本身强调数很多，考点应该是如何不通过将数存入内存
找到答案。向上面所说的一个数一个bit不现实吧，怎么找到这个数的对应的bit位本来
就是一个够gay的问题。而且100mb和一亿这样的数字根本没有任何参考价值。要是内存
1k，数字1b咋办？
【在 b********e 的大作中提到】
: 开始也这样想的，但是最大的可能就是int(or long)的最大值，再加1就溢出了
|
