当前位置: 代码迷 >> 综合 >> 腾讯面试:bitmap判断其中是否有相同元素
  详细解决方案

腾讯面试:bitmap判断其中是否有相同元素

热度:61   发布时间:2024-02-26 11:28:28.0

       有50亿个uint32元素,判断其中是否有相同元素。

       看到这个大数据的题目,还有内存限制,就用bitmap。在数据量比较少的情况下用hash表也是个不错的方法。

        这里要用2个bitmap,占用总内存1G。

        这里我们算算内存:uint32总共4个字节,根据bitmap的思想,2^32可以存储uint32数。

        因为一个是8个位,2^32/8 = 0.5 * 2^30= 0.5G(2^30 = 大约1百万)

       1G = 1024M = 1024 * 1024 B,所有说内存够用

     

       2个bitmap说一个数对应2个二进制位00(出现0次)    01(出现1次)  10(出现2次)  11(出现多次)