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

拼搏现实的明天。 2022-09-10 15:10 106阅读 0赞

> 文章来源于：[https://wwww.iamshuaidi.com][https_wwww.iamshuaidi.com]，一个专注于校招，面试，面经的编程网站

![2fe16887fea3bc99b576c2fbd8e028e2.png][]

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

![03c92da1335dc18757e9d4ce580982b4.png][]

![c39546cc2d135b6d1f7a6d6bed6ce9e6.png][]

![a4db55e20bbfadb2d6b3d5b08d68b121.png][]

![45297e512b50c3a4df4b935d982ad72e.png][]

![c69fe486e51fb2e04602048fb2551781.png][]

![554cfc7f673689d0b5c1f3b62986f398.png][]

![ad4da7794ebdb09f45d3e501aef6f927.png][]

![fed515a090ae1d86b36c612ff3c17b8b.png][]

![f96a54267726e15966e12195bce35e84.png][]

![2d5e7c0a0ef89a943311b8c01f87bb5b.png][]

![a790c76f6d5c6a776f78817f15344cfc.png][]

**【请教大神】**

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

![30ed5cf8a75a06cad90b7a72edd4ac95.png][]

![e35007e33631fc86a0e7b6ea1509c098.png][]

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

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

![92de084e4e20f6c939ed106077a4fa09.png][]

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

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

![9c24204a62d7275c098245c0d22afe76.png][]

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

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

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

**【更好方案】**

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

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

![1e4d61de3e97cead3e2821bafc7e8084.png][]

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

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

![36f58d5c4e1eb7e85522d952580040bd.png][]

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

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

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

![5fb05c00504345ad30a10bfd20ffee0b.png][]

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

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

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

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

![604cec5f7e0eeddef5eeae8bfa0b70d5.png][]

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

![a334ade1ce3e8c646d38b9b78831ac41.png][]

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

**【吕老师的课】**

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

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

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

![ed190df5fcc0714fa09e4bc7dd43a004.png][]

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

如果数据是1 2 3 4 6 7……这种的，那么可以用(1,4)和(6,2)来表示，这样一来，连续的数都变成了2个数表示。 来了一个新数之后，就用二分法进行查找了。

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

![849c463fe90931809cbdb11e8d89b580.png][]

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

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

**【课后】**

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

![8d60deb1d2e848f93418bbc305881251.png][]

![01f1b1765b201a7a49ec919c09ff6cd0.png][]

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

大家好，我是帅地，目前也正在更[面试][Link 1]，[面经][Link 2]，[算法][Link 3] 等硬核文章，点击[我的头像][Link 2]，你会发现相见恨晚，如果觉得文章不过，也别吝啬你的赞哦，嘻嘻

更多面试现场文章：

[1. 如何判断一个数是否在40亿个整数中？][1. _40]

[2. 如何实现可以获取最小值的栈？][2.]

[3. 记一次 shopee 面试：最小栈的最优解][3. _ shopee]

[4. 为什么要分稳定排序和非稳定排序？][4.]

[5. 如何编程解决华容道问题？][5.]

[6. 如何找到字符串中的最长回文子串？][6.]

[7. 如何在500w个单词中统计特定前缀的单词有多少个?][7. _500w]

[8. 如何在10亿数中找出前1000大的数？][8. _10_1000]

[9. 如何编程获得最多的年终红包奖？][9.]

[10. 如何编程解决朋友圈个数问题？][10.]

[11. 如何设计可自学习的五子棋AI？][11. _AI]

[12. 为什么MySQL数据库要用B+树存储索引？][12. _MySQL_B]

[13. 记一道字节跳动面试：变形的链表反转][13.]

[14. 记一次手撕算法面试：字节跳动的面试官把我四连击了][14.]

[15. 记一次阿里笔试：一行代码解决约瑟夫环问题的][15.]

[16. 记一次阿里面试：面试挂在了 LRU 缓存算法设计上][16. _ LRU]

[17. 记一次网易笔试：前缀和的应用][17.]

[18. 游戏中的敏感词过滤是如何实现的？][18.]

[19. 如何只用2GB内存从20/40/80亿个整数中找到出现次数最多的数][19. _2GB_20_40_80]

[https_wwww.iamshuaidi.com]: https://wwww.iamshuaidi.com
[2fe16887fea3bc99b576c2fbd8e028e2.png]: /images/20220829/0916605bbe2048f0a1542d9a078229c6.png
[03c92da1335dc18757e9d4ce580982b4.png]: /images/20220829/17e820ba8fa24af2b625ef1fd34b4d78.png
[c39546cc2d135b6d1f7a6d6bed6ce9e6.png]: /images/20220829/2784d6a2cda54176b1f9e84eb3b34f5e.png
[a4db55e20bbfadb2d6b3d5b08d68b121.png]: /images/20220829/bf60c743920e46dea15847db49f2f7c3.png
[45297e512b50c3a4df4b935d982ad72e.png]: /images/20220829/394cfef40c8242ef8f3bc318cd8ec233.png
[c69fe486e51fb2e04602048fb2551781.png]: /images/20220829/b674af33e1c642dc81305e646eb14ebe.png
[554cfc7f673689d0b5c1f3b62986f398.png]: /images/20220829/40414a5b95174b798978648f4414a25c.png
[ad4da7794ebdb09f45d3e501aef6f927.png]: /images/20220829/34dd09973b614e638ec2ed00f282ae06.png
[fed515a090ae1d86b36c612ff3c17b8b.png]: /images/20220829/6ecd16a44a6a423397ad659ee3455aa0.png
[f96a54267726e15966e12195bce35e84.png]: /images/20220829/e1ab892700ae4897b339ac375057fdbd.png
[2d5e7c0a0ef89a943311b8c01f87bb5b.png]: /images/20220829/8b806511841e4739a9afc81e651fbeed.png
[a790c76f6d5c6a776f78817f15344cfc.png]: /images/20220829/bb220657c1bd49c18c6224915d4a777e.png
[30ed5cf8a75a06cad90b7a72edd4ac95.png]: /images/20220829/3ad04c2b5a0b4794ae94b49260b355b0.png
[e35007e33631fc86a0e7b6ea1509c098.png]: /images/20220829/8829af63741041409d7e9925bf25b908.png
[92de084e4e20f6c939ed106077a4fa09.png]: /images/20220829/2bdce6fe8b1d42b2858aabc44c48e9a7.png
[9c24204a62d7275c098245c0d22afe76.png]: /images/20220829/205b4e80165b4944b282826531a36bc6.png
[1e4d61de3e97cead3e2821bafc7e8084.png]: /images/20220829/ec161db2dc9f427fa32eeaede64e1bce.png
[36f58d5c4e1eb7e85522d952580040bd.png]: /images/20220829/192dba8d63584728ab3c70c963dd0e81.png
[5fb05c00504345ad30a10bfd20ffee0b.png]: /images/20220829/d0c61fab4fa4479d8d6fd0e0694f8d43.png
[604cec5f7e0eeddef5eeae8bfa0b70d5.png]: /images/20220829/681c834e35f54c3e92d9589a0451fefc.png
[a334ade1ce3e8c646d38b9b78831ac41.png]: /images/20220829/66833dde829b421485a0c059a3ea17d6.png
[ed190df5fcc0714fa09e4bc7dd43a004.png]: /images/20220829/321a6c20b85b4b2b935a7a82f774528e.png
[849c463fe90931809cbdb11e8d89b580.png]: /images/20220829/c0d9bc477e184fdf9bfb6814ec7e4830.png
[8d60deb1d2e848f93418bbc305881251.png]: /images/20220829/d88c00d8b3ad48278b6a3265ba362848.png
[01f1b1765b201a7a49ec919c09ff6cd0.png]: /images/20220829/9e35694c241249bab50b93d51e965c11.png
[Link 1]: https://www.iamshuaidi.com/3194.html
[Link 2]: https://www.iamshuaidi.com/
[Link 3]: https://www.iamshuaidi.com/155.html
[1. _40]: https://www.iamshuaidi.com/?p=111
[2.]: https://www.iamshuaidi.com/?p=116
[3. _ shopee]: https://www.iamshuaidi.com/?p=118
[4.]: https://www.iamshuaidi.com/?p=121
[5.]: https://www.iamshuaidi.com/?p=125
[6.]: https://www.iamshuaidi.com/?p=127
[7. _500w]: https://www.iamshuaidi.com/?p=129
[8. _10_1000]: https://www.iamshuaidi.com/?p=131
[9.]: https://www.iamshuaidi.com/?p=133
[10.]: https://www.iamshuaidi.com/?p=135
[11. _AI]: https://www.iamshuaidi.com/?p=137
[12. _MySQL_B]: https://www.iamshuaidi.com/?p=139
[13.]: https://www.iamshuaidi.com/?p=141
[14.]: https://www.iamshuaidi.com/?p=143
[15.]: https://www.iamshuaidi.com/?p=145
[16. _ LRU]: https://www.iamshuaidi.com/?p=147
[17.]: https://www.iamshuaidi.com/?p=149
[18.]: https://www.iamshuaidi.com/?p=151
[19. _2GB_20_40_80]: https://www.iamshuaidi.com/?p=153