算法通关村第十五关 | 白银 | 海量数据场景下的热门算法题

2023-12-13 13:08:37

1.从 40 个亿中产生一个不存在的整数

可以采用位图存储数据,申请一个 bit 类型的数组 bitArr ,每个位置只表示 0 或者 1 状态,可以将占用内存缩小为使用哈希表的 1/32 。

遍历给定的 40 亿个数,遇到数时就将 bitArr 相应位置设置为 1 。

遍历结束后,再遍历 bitArr ,哪个位置上的值是 0 ,那这个数就不在 40 亿个数中。

假如现在只有 10 MB 内存空间可用,就可以考虑使用分块的方法。通过时间换取空间。

将数据平均分成多个区间,只计算区间内的数据,总有一个区间的数是少于其他区间的平均计数的,那就可以从这个区间里用位图的方式找到没出现过的数。

2.用 2GB 内存在 20 亿个整数中找到出现次数最多的数

极端情况下这些数可以全部都不相同,那么内存占用会非常大。

使用哈希函数将大文件分为小文件,同一种数是不会被分到不同的小文件上的,就可以得到每个小文件中出现最多的数以及次数统计。

3.从 100 亿个 URL 中查找重复项

同样使用哈希函数将文件拆分,拆分要注意资源限制,要明确将数据分到若干台机器或者分为若干个文件。

4. 40 亿个非负整数中找到出现两次的数

与第一位相同,使用位图,但是这次要用两倍大小的位图解决问题。

用两位表示一个数据,初始为 00 ,每次出现都加一,且加到 11 之后不再变动,这样最后两位为 10 的位置表示的就是出现了两次的数。

如果对您有帮助,请点赞关注支持我,谢谢! ?
如有错误或者不足之处,敬请指正! ?
个人主页:星不易 ?
算法通关村专栏:不易|算法通关村 ?

文章来源:https://blog.csdn.net/m0_57130776/article/details/134937118
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。