如何判断一个数是否在 40 亿个整数中？

清疚 2021-12-14 23:15 258阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | channingbreeze

来源 | 互联网侦察

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

今天他就去BAT中的一家面试了。

简单的自我介绍后，面试官给了小史一个问题。

**【面试现场】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

**题目：我有40亿个整数，再给一个新的整数，我需要判断新的整数是否在40亿个整数中，你会怎么做？**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 11]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 12]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 13]

![640?wx\_fmt=png][640_wx_fmt_png]

**【请教大神】**

小史回到学校，把面试的情况和计算机学院的吕老师说了一下。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 14]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 15]

小史忙拉着吕老师问，为什么我说分8次加载数据，面试官会说太慢了呢？

吕老师：哈哈，从磁盘加载数据是磁盘io操作，是非常慢的，你每次都要加载这么大的数据，还要8次，我估计你找一个数的时间可以达到分钟甚至小时级了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 16]

小史：那如果是你，你会怎么办呢？

吕老师：其实面试官已经提示得比较明显了，他说给你一批机器，就是暗示你可以用分布式算法。你把数据分散在8台机器上，然后来一个新的数据，8台机器一起找，最后再汇总结果就行了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 17]

小史：这样的话能快多少？

吕老师：这样应该能达到秒级。小史，你可以自己分析分析。

小史：我想想……哦，这样做的话，因为每台机器都可以一次性把数据读入内存，在比较的时候不用来回加载数据了，所以可以节省加载数据的开销！这真是个好办法。

**【更好方案】**

吕老师：其实这并不是最好方法，我这还有一种毫秒级的方法，想不想知道啊？

小史：当然想啊，快教教我。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 18]

小史：哦，对哦，这样我就申请40亿个位就好了，新的数转换成一个位，然后判断一下这个位是0还是1就行了。

吕老师：小史啊，考虑问题要考虑清楚啊，如果是40亿个位，那么这40亿个位哪些是0，哪些是1呢？来了一个新的数，怎么判断是否在40亿个位之中？

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 19]

小史：我想想，对啊，40亿个位，40亿个数，那么每个位都是1，这。。。

吕老师：其实你可以想想，32位int的范围，总共就是2的32次方，大概42亿多点。所以你可以申请2的32次方个位。

小史：意思是我把整个整数范围都覆盖了，哦，对哦。这样一来，就可以做了，1代表第一个位，2代表第二个位，2的32次方代表最后一个位。40亿个数中，存在的数就在相应的位置1，其他位就是0。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 20]

吕老师：没错，那来了一个新的数呢？

小史：新的数就去找相应的位，比如来了一个1234，就找一下第1234位，如果是1就存在，是0就不存在啦。

吕老师：没错，那么这样的话，需要多大内存呢？

小史：我想想啊，2的32次方个位，相当于2的29次方个字节，哇，才500MB，真是节省了不少内存呢。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 21]

小史：这么厉害的算法，你是怎么想到的？

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 22]

吕老师：其实这是一种非常有名的大数据算法，叫位图法，英文名叫bitmap。顾名思义，就是用位来表示状态，从而节省空间。明天正好我有一节课，就讲位图法，你可以来听一听。

**【吕老师的课】**

第二天，吕老师开始上课，他一开始就抛出了小史遇到的面试题。

吕老师：同学们，这道题是BAT公司的一道面试题，大家有什么思路吗？

话音刚落，蛋哥就站起来回答。蛋哥是吕老师最得意的门生，以思维活跃著称。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 23]

蛋哥：我觉得可以这样。首先，32位int的范围是42亿，40亿整数中肯定有一些是连续的，我们可以先对数据进行一个外部排序，然后用一个初始的数和一个长度构成一个数据结构，来表示一段连续的数，举个例子。

如果数据是1 2 3 4 6 7……这种的，那么可以用(1,4)和(6,2)来表示，这样一来，连续的数都变成了2个数表示。

来了一个新数之后，就用二分法进行查找了。

这样一来，最差情况就是2亿多的断点，也就是2亿多的结构体，每个结构体8个字节，大概16亿字节，1.6GB，在内存中可以放下。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 24]

吕老师：嗯，非常好，不仅给出了方案，还能主动分析空间和可行性。

小史听完后深感佩服，问题的解决方法绝对不止一种，只要肯动脑筋，即使没有学过bitmap算法，也能有别的方法来解决问题。

**【课后】**

下课后，小史又找到吕老师。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 25]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 26]

吕老师：但是你的理解能力还是很强的，很多东西一听就懂，这可不是谁都能做到的。

多多关注这个公众号，多看一看一线互联网面试现场，我相信你一定有收获的。

## END ##

## ![640?wx\_fmt=png][640_wx_fmt_png 1] ##

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 2] 你点的每个“在看”，我都认真当成了喜欢

[640_wx_fmt_jpeg]: /images/20211214/43f3232a88e54c079b815edb47ebc776.png
[640_wx_fmt_jpeg 1]: /images/20211214/33b32e382623475eab7ab168e92793aa.png
[640_wx_fmt_jpeg 2]: /images/20211214/a483aafc26bb44fbbe1105e1844e9d4e.png
[640_wx_fmt_jpeg 3]: /images/20211214/81a27cdcb42c489fa10375695103bfa2.png
[640_wx_fmt_jpeg 4]: /images/20211214/12f3a0ae05d04567a9a6e686e3ce6f61.png
[640_wx_fmt_jpeg 5]: /images/20211214/8841e4e667a94c3e91472c40bd23a459.png
[640_wx_fmt_jpeg 6]: /images/20211214/8bed8d11c58348e6b99072366d3934cd.png
[640_wx_fmt_jpeg 7]: /images/20211214/d4bfa9b2a1b14fd79e19b0ab324510e5.png
[640_wx_fmt_jpeg 8]: /images/20211214/fca12d638f5b4352994aa983394be337.png
[640_wx_fmt_jpeg 9]: /images/20211214/6aa0f85fe1984e9da932842cbf58d162.png
[640_wx_fmt_jpeg 10]: /images/20211214/149b33a4d57041e8bc3e70aa305eadc8.png
[640_wx_fmt_jpeg 11]: /images/20211214/cb0c9fa7e3a8426fba6ca3c1305eb58a.png
[640_wx_fmt_jpeg 12]: /images/20211214/1fd583e489bd4c74803f3d97157b34eb.png
[640_wx_fmt_jpeg 13]: /images/20211214/151c0ebce0db4f43aaa478d4b86e958c.png
[640_wx_fmt_png]: /images/20211214/71abe5f8d21b41cbace7fe2998b9f075.png
[640_wx_fmt_jpeg 14]: /images/20211214/c2d4a279f7b94fbc92a865b4e6d21f3f.png
[640_wx_fmt_jpeg 15]: /images/20211214/1acbf0f42ca64739b7356e1970ac77b2.png
[640_wx_fmt_jpeg 16]: /images/20211214/d068181408ff44b2a9e817154c077aa7.png
[640_wx_fmt_jpeg 17]: /images/20211214/c5c91d715f2f4f01aef187185d2d75bf.png
[640_wx_fmt_jpeg 18]: /images/20211214/8b64afc931394cc3b34c9ae71c5a610a.png
[640_wx_fmt_jpeg 19]: /images/20211214/4dece557c3e94e59874e3de93103c3d2.png
[640_wx_fmt_jpeg 20]: /images/20211214/b81e5cacbe9b4fc0b3939ac6ba43917a.png
[640_wx_fmt_jpeg 21]: /images/20211214/681a23db4de34827a422798697ed5198.png
[640_wx_fmt_jpeg 22]: /images/20211214/0ca0efb011664b61b5563795436e3834.png
[640_wx_fmt_jpeg 23]: /images/20211214/a4efa42fca534bb58451d5bc15b85fc5.png
[640_wx_fmt_jpeg 24]: /images/20211214/44cfe023c8fa4a5b9f7b4a96adbc3218.png
[640_wx_fmt_jpeg 25]: /images/20211214/0b4122545b8a4e1a98d6585c244846a2.png
[640_wx_fmt_jpeg 26]: /images/20211214/181dec0939204cdbb0cd4fcdaa598938.png
[640_wx_fmt_png 1]: /images/20211214/253a16817f9d4a4abfac1ac3e56ca842.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 2]: /images/20211214/7f5737e7917a40979423b2e16677e36d.png