今天有个同事问我一个问题？“如果有40亿整型数，如何判断一个整数是否在这40亿整型数中呢？”
我觉得这是个非常有意思的问题。如果是你的话，你会怎么做呢？实际上我觉得应用算法上的话，重在一个解题思路，希望就以下我一个简单思路，给大家一个启发。
先讲下我的思路吧，实际上对于这种问题我会把它归并到算法优化这种类型中，我一般处理这种问题的思路就是，先想出一个最“笨”的方法，然后对这个笨方法进行逐步优化，而优化的方式也无非是，降低时间复杂度，降低空间复杂度以及使用分页，并行的方式。下面是我做这个题的思路：
1.先想个“笨”方法
听到这个问题以后我的第一感觉就是要，并行，分块/二分查找，不过为了思路更为清晰，咱们使用一个最基础的，顺序查找。
最简单的查找方式莫过于循环了，开辟一个40亿整型数空间的数组，去遍历这个40亿的数组，对比其中是否有与这个数相等的数存在。这样虽然得出了结果，但是咱们分析下这个数据，40亿整型数，1个整型4个字节，40亿就是160亿字节，相当于近16G！那就一台一般的电脑而言，这一关就很难达到。
2.分析问题，尝试解决上一步最突出的问题（循环）
上一步中最突出的问题大概就是使用的内存空间了吧，然后其次就是这恐怖的大循环，那后面就会想到几种解决方式。
空间复杂度方面：
1.将数据存磁盘中，解决了内存不足的情况。「我只能说，没毛病，存了就解决这个了，但是存的话就设计到了磁盘的IO了，但是这数据读取速度可是差的不是一点半点」
2.拆分存储，一台计算机存不下的话，那就用多台设备分割下数据，分别存储和计算。「非常好的一个思路，现在分布式存储就有采用这一思路进行处理，这在实际应用场景应该很多，在应用场景下其实现在很多大数据已然用到，可以去了解下spark啥的，不过对于这个问题前提是有多台机器」
3.缩小数据，整型数最大为2的32次幂减1，也就是4294967295个数，如果用一个bit代表对应的数是否存在，也就是会成为转化为data[i]是否是1的问题，判断是否存在「这种方法我个人想到是极好的，1个4字节长变为了1bit，16G/32=500M，直接到了可运行范围了，实际应用场景中，判断一个用户的活跃度的时候，我经常采用此种方式。划重点」
时间复杂度方面：
1.无序转有序，用分块查找，二分查找「先排序了，然后再二分查找」
2.二叉排序树「这个我就那么一说」
3.哈希「我也就那么一说」
4.bitmap算法「大数据中常用的一种算法，说白了跟上门“缩小数据”的想法，具体该把数如何放对应bit位，位移和映射的方法」
3.选出一个最适合你应用场景的方法
就以上讨论而言，我觉得直接将整型数转为bit，使用bitmap算法，就可以很好的解决问题了，哈哈，如果有更好的解决方案可以留言告诉我，一起进步
希望能为大家提供一种日常解决问题的思路
网友评论