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

红太狼 2023-06-13 09:11 10阅读 0赞

作者 | channingbreeze

来源公众号 | 互联网侦察

声明：已获作者授权转载

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

![v2-b8821e07cb84fa4cf0bdaa1adeca49eb\_b.jpg][v2-b8821e07cb84fa4cf0bdaa1adeca49eb_b.jpg]

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

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

**【面试现场】**

![v2-f1c6ced20f39d702ff9cef0d30d7a027\_b.jpg][v2-f1c6ced20f39d702ff9cef0d30d7a027_b.jpg]

![v2-4184ace6a63d3a913712a120bccb30ba\_b.jpg][v2-4184ace6a63d3a913712a120bccb30ba_b.jpg]

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

![v2-c2e24b5497501d8238c8bd68604db077\_b.jpg][v2-c2e24b5497501d8238c8bd68604db077_b.jpg]

![v2-4e97e8569a78853f96ae18df36c5b11c\_b.jpg][v2-4e97e8569a78853f96ae18df36c5b11c_b.jpg]

![v2-123def64ea770c42db2a5bbb9617115f\_b.jpg][v2-123def64ea770c42db2a5bbb9617115f_b.jpg]

![v2-d38b4edcee81cd5d8a8288d360b738ac\_b.jpg][v2-d38b4edcee81cd5d8a8288d360b738ac_b.jpg]

![v2-1a0fe50547a38559e879b249ad100547\_b.jpg][v2-1a0fe50547a38559e879b249ad100547_b.jpg]

![v2-911f4526f8a13aafaa27d2c1ca422612\_b.jpg][v2-911f4526f8a13aafaa27d2c1ca422612_b.jpg]

![v2-99ebc5223c7140e3dc4993a184c1c306\_b.jpg][v2-99ebc5223c7140e3dc4993a184c1c306_b.jpg]

![v2-0a1370fbbfac3df9bb1505f9264fc5a4\_b.jpg][v2-0a1370fbbfac3df9bb1505f9264fc5a4_b.jpg]

![v2-fdd5552b74922d2350c67e3b9121bde0\_b.jpg][v2-fdd5552b74922d2350c67e3b9121bde0_b.jpg]

![v2-e3d7fb96c929d281c0eebbb6489343c9\_b.jpg][v2-e3d7fb96c929d281c0eebbb6489343c9_b.jpg]

![v2-24954867c4a35dd75f57bbeda7e082f3\_b.jpg][v2-24954867c4a35dd75f57bbeda7e082f3_b.jpg]

**【请教大神】**

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

![v2-e20a1550a20cec50d925e1d449b7a09d\_b.jpg][v2-e20a1550a20cec50d925e1d449b7a09d_b.jpg]

![v2-0cdcb39c9027a229d437e7ab4e62a8a7\_b.jpg][v2-0cdcb39c9027a229d437e7ab4e62a8a7_b.jpg]

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

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

![v2-53c8c1374a7124c7e6710220f8ef6f9e\_b.jpg][v2-53c8c1374a7124c7e6710220f8ef6f9e_b.jpg]

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

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

![v2-f1a53bb73353f140cf6db0f37dc88bba\_b.jpg][v2-f1a53bb73353f140cf6db0f37dc88bba_b.jpg]

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

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

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

**【更好方案】**

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

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

![v2-ad6d57a5c2ef4653b6ce0f00e2c05485\_b.jpg][v2-ad6d57a5c2ef4653b6ce0f00e2c05485_b.jpg]

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

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

![v2-cfb5a1079d8607493db483c487713022\_b.jpg][v2-cfb5a1079d8607493db483c487713022_b.jpg]

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

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

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

![v2-7fb59c65965f34905c30d2baf7ebcd68\_b.jpg][v2-7fb59c65965f34905c30d2baf7ebcd68_b.jpg]

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

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

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

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

![v2-da24a556f5d9aceb56fc8e71dffeea0b\_b.jpg][v2-da24a556f5d9aceb56fc8e71dffeea0b_b.jpg]

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

![v2-386a4812c0de872b6c4471f752c6c38c\_b.jpg][v2-386a4812c0de872b6c4471f752c6c38c_b.jpg]

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

**【吕老师的课】**

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

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

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

![v2-9114e933679a504397d3312adb77e33e\_b.jpg][v2-9114e933679a504397d3312adb77e33e_b.jpg]

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

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

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

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

![v2-beb8d2db83212a608db6b7ff006a45bd\_b.jpg][v2-beb8d2db83212a608db6b7ff006a45bd_b.jpg]

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

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

**【课后】**

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

![v2-9bffe619815d755f95aad1715ede8b62\_b.jpg][v2-9bffe619815d755f95aad1715ede8b62_b.jpg]

![v2-3296cff0294d661fe0219b7a47bfeab1\_b.jpg][v2-3296cff0294d661fe0219b7a47bfeab1_b.jpg]

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

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

本文作者是我的好朋友**欣哥，原文链接如下：**

[【面试现场】如何判断一个数是否在40亿个整数中？][40]

![v2-0f898b0b78410a4705ea72eaa3a7dc42\_b.jpg][v2-0f898b0b78410a4705ea72eaa3a7dc42_b.jpg]

**我的专栏：**

[和程序员小吴一起学算法][Link 1]

**❤️ 看完三件事：**  
如果你觉得这篇内容对你挺有启发，我想邀请你帮我三个忙：

1.  **点赞，**让更多的人也能看到这篇内容（**收藏不点赞，都是耍流氓 -\_-**）
2.  **关注我和专栏，**让我们成为长期关系
3.  **关注公众号「五分钟学算法」，**第一时间阅读最新的算法文章，公众号后台回复 1024 送你 50 本 算法编程书籍。

![v2-7d84a7f4361bd5f8d21b98b9edb0b1b4\_b.jpg][v2-7d84a7f4361bd5f8d21b98b9edb0b1b4_b.jpg]

[v2-b8821e07cb84fa4cf0bdaa1adeca49eb_b.jpg]: https://img-blog.csdnimg.cn/img_convert/c7eb054deaef0674bab84181e1164b24.png
[v2-f1c6ced20f39d702ff9cef0d30d7a027_b.jpg]: https://img-blog.csdnimg.cn/img_convert/e22357a9e7b4f11043a9b7fcf3bded13.png
[v2-4184ace6a63d3a913712a120bccb30ba_b.jpg]: https://img-blog.csdnimg.cn/img_convert/4832332b0c8294f36d5722c6da2a5fc5.png
[v2-c2e24b5497501d8238c8bd68604db077_b.jpg]: https://img-blog.csdnimg.cn/img_convert/1692aaff6154e75aaf37c9c21467d287.png
[v2-4e97e8569a78853f96ae18df36c5b11c_b.jpg]: https://img-blog.csdnimg.cn/img_convert/14926ad45d84b7649c5844759e0f0acf.png
[v2-123def64ea770c42db2a5bbb9617115f_b.jpg]: https://img-blog.csdnimg.cn/img_convert/f7f32ae887ef3b89c5545e2208bf7bb6.png
[v2-d38b4edcee81cd5d8a8288d360b738ac_b.jpg]: https://img-blog.csdnimg.cn/img_convert/e29b49d0701c45ba1e98cce216dc017d.png
[v2-1a0fe50547a38559e879b249ad100547_b.jpg]: https://img-blog.csdnimg.cn/img_convert/286b0a4c47dc2d9fba7f4f9f032e1418.png
[v2-911f4526f8a13aafaa27d2c1ca422612_b.jpg]: https://img-blog.csdnimg.cn/img_convert/0b8f0f156a5ecd595e1a61fddbaecd0d.png
[v2-99ebc5223c7140e3dc4993a184c1c306_b.jpg]: https://img-blog.csdnimg.cn/img_convert/a3ad210af0bee85f8250d2247ca4a3d0.png
[v2-0a1370fbbfac3df9bb1505f9264fc5a4_b.jpg]: https://img-blog.csdnimg.cn/img_convert/91c14bcf4068b7de1baa9b1e8d0414da.png
[v2-fdd5552b74922d2350c67e3b9121bde0_b.jpg]: https://img-blog.csdnimg.cn/img_convert/d2dbb3c9bcf30e5c3e7c4a1c3c660e91.png
[v2-e3d7fb96c929d281c0eebbb6489343c9_b.jpg]: https://img-blog.csdnimg.cn/img_convert/80953cef70ff0c672ac28c213e351ce2.png
[v2-24954867c4a35dd75f57bbeda7e082f3_b.jpg]: https://img-blog.csdnimg.cn/img_convert/1c07efc40117670a2dd9bb807341feb2.png
[v2-e20a1550a20cec50d925e1d449b7a09d_b.jpg]: https://img-blog.csdnimg.cn/img_convert/6e019c8333f879f6e672d9649b7f2830.png
[v2-0cdcb39c9027a229d437e7ab4e62a8a7_b.jpg]: https://img-blog.csdnimg.cn/img_convert/f15c73b078662f926407381a01815ef2.png
[v2-53c8c1374a7124c7e6710220f8ef6f9e_b.jpg]: https://img-blog.csdnimg.cn/img_convert/7327dfcb3f0b694a679b7509ce80927d.png
[v2-f1a53bb73353f140cf6db0f37dc88bba_b.jpg]: https://img-blog.csdnimg.cn/img_convert/045b49517f68aa00f5109859b823a5bc.png
[v2-ad6d57a5c2ef4653b6ce0f00e2c05485_b.jpg]: https://img-blog.csdnimg.cn/img_convert/0737bb36ced6bccec0d3937a68d4a18f.png
[v2-cfb5a1079d8607493db483c487713022_b.jpg]: https://img-blog.csdnimg.cn/img_convert/bc2ba09e36347b50df8efc0dc659a7e5.png
[v2-7fb59c65965f34905c30d2baf7ebcd68_b.jpg]: https://img-blog.csdnimg.cn/img_convert/75371965369255c5721358ad91c1252b.png
[v2-da24a556f5d9aceb56fc8e71dffeea0b_b.jpg]: https://img-blog.csdnimg.cn/img_convert/0342fd48883b9be8811270e1bef03a56.png
[v2-386a4812c0de872b6c4471f752c6c38c_b.jpg]: https://img-blog.csdnimg.cn/img_convert/9b416376e05fa700f825900c3f0d5522.png
[v2-9114e933679a504397d3312adb77e33e_b.jpg]: https://img-blog.csdnimg.cn/img_convert/7476d2639adf34ac951dd1ba4d2ab7d1.png
[v2-beb8d2db83212a608db6b7ff006a45bd_b.jpg]: https://img-blog.csdnimg.cn/img_convert/0c893f28dcc3ed35a5762d8c6247b485.png
[v2-9bffe619815d755f95aad1715ede8b62_b.jpg]: https://img-blog.csdnimg.cn/img_convert/cbab7e7a8f024a227bfb3ad51f11a827.png
[v2-3296cff0294d661fe0219b7a47bfeab1_b.jpg]: https://img-blog.csdnimg.cn/img_convert/4533b4c269a3240094ab28626b2d2cf4.png
[40]: https://link.zhihu.com/?target=https%3A//mp.weixin.qq.com/s/M-9OXISosrqRI08QIDJiPA
[v2-0f898b0b78410a4705ea72eaa3a7dc42_b.jpg]: https://img-blog.csdnimg.cn/img_convert/9a6726d5e2830d4d7be04d2e92df52cc.png
[Link 1]: https://zhuanlan.zhihu.com/c_1039097450233057280
[v2-7d84a7f4361bd5f8d21b98b9edb0b1b4_b.jpg]: https://img-blog.csdnimg.cn/img_convert/cfb13222504ffb992caf217eb0c122a5.png