海量数据小内存!只出现两次的数以及中位数怎么找
创始人
2024-04-27 05:40:00
0

文章目录

    • 题目一
    • 题目二

实际上类似的题目类似的解法在之前已经有介绍过

海量数据小内存!如何找到高频数
海量数据小内存!从未出现过的数在哪里

题目一

如何在 40 亿个无符号整数中找到出现次数只有两次的那些数,在只提供 1 G 内存的条件下

解答

方法一【分流】

单纯的将这些无符号整数放到 HashMap 中,大概率是会爆内存的,我们可以选择将这些无符号整数分流到很多个小文件中,然后使用 HashMap 对小文件中的数出现的频率进行统计,将只出现过两次的数保存到结果文件中

那么分流的方法就是,遍历这 40 亿个无符号整数,给他们都调用一个 Hash 函数,将结果模上小文件数,就可以实现将这些数均匀的分散的分流到小文件中

至于需要模上多少,即小文件的数量有多少,那就取决于提供的内存有多少,支持存多少条 Hash 记录。

比如,一条 Hash 记录至少 8 字节,就算会有其他的空间消费,我们就算一条记录 16 个字节,那么 1 G 可以申请 0.6 亿的数据,那么可以将 40 亿个数分成 70 个文件。其实,只要空间够用,分配较为合理,都是可以的

在这里插入图片描述

方法二【位图】

根据之前的文章,我们可以知道,位图中的一个位是可以表示数有没有出现过的,比如出现过就标记为 1,始终没有出现过就一直都是 0。

那么现在想要表示出现两次的数,那么我们就可以使用两位来表示。00 表示该数从未出现过,01表示该数只出现过 1 次,10,表示该数出现过两次,11 表示该数出现超过两次。

40 亿个数,每个数使用两位,那么也就 80 亿位,即 10 亿字节,如果按照 1024 进行换算,消耗的内存是不会超过 1 G的

题目二

如何在 40 亿个无符号整数中找到中位数,在只提供 10 KB 的内存的条件下

解答

我们就把提供的 10 KB 内存统统用来申请无符号整形数组,看看最多能够不申请多少大小,并且数组的大小得是 2 的某次方,计算可得可申请大小为 2048 的无符号整形数组 array

在这里插入图片描述

那么我们就将无符号整数的范围(0~232-1)分成 2048 份,一定能够均分,每份包含的数据大小为 2 的 21 次方

在这里插入图片描述

然后,我们就需要遍历这 40 亿个数,计算各个值应该属于哪个范围,将数组 array 对应下标的值加一,比如 500 这个数,显而易见应该属于 0 ~ Y-1 这个范围,所以 array[0]++

遍历完全后,我们将每个范围的值进行累加,看看哪个范围刚好让累加值等于或者刚好超过 20 亿,那么中位数一定在那个范围中

在这里插入图片描述

如上图所示,可以发现累加到 array[2] 时,值刚好突破了 20 亿,那么就可以确定中位数就在 array[2] 所代表的的数值范围内。

接下来就是将目标范围内的数据(7亿)继续等分成 2048 份(每份范围大小为 2 的 10 次方),由于 array[0] 和 array[1] 的累加和为 15 亿,那么中位数就是 array[2] 中的第 5 亿个数(从小到大)

在这里插入图片描述

和上面的步骤一样,将中位数定在了 array[1] 区间范围内的数中,以此类推,最后总能找到目标数

相关内容

热门资讯

安卓双系统添加应用,轻松实现多... 你有没有想过,你的安卓手机里可以同时运行两个系统呢?听起来是不是很酷?想象一边是熟悉的安卓系统,一边...
pipo安卓进系统慢,探究pi... 最近是不是发现你的Pipo安卓系统更新或者运行起来特别慢?别急,今天就来给你好好分析分析这个问题,让...
怎样使用安卓手机系统,安卓手机... 你有没有发现,安卓手机已经成为我们生活中不可或缺的一部分呢?从早晨闹钟响起,到晚上睡前刷剧,安卓手机...
双系统安卓安装caj,轻松实现... 你有没有想过,你的安卓手机里装上双系统,是不是就能同时享受安卓和Windows系统的乐趣呢?没错,这...
安卓使用ios系统教程,安卓用... 你是不是也和我一样,对安卓手机上的iOS系统充满了好奇?想要体验一下苹果的优雅和流畅?别急,今天我就...
安卓系统gps快速定位,畅享便... 你有没有遇到过这样的情况:手机里装了各种地图导航软件,但每次出门前都要等上好几分钟才能定位成功,急得...
安卓手机系统更新原理,原理与流... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,让我来给你揭秘一下安卓手机系统...
安卓系统通知管理,全面解析与优... 你有没有发现,手机里的通知就像是一群调皮的小精灵,时不时地跳出来和你互动?没错,说的就是安卓系统的通...
安卓系统手机哪买,揭秘哪里购买... 你有没有想过,拥有一部安卓系统手机是多么酷的事情呢?想象你可以自由安装各种应用,不受限制地探索各种功...
安卓系统 ipv4,基于安卓系... 你知道吗?在智能手机的世界里,有一个系统可是无人不知、无人不晓,那就是安卓系统。而在这个庞大的安卓家...
目前安卓是什么系统,探索安卓系... 亲爱的读者,你是否曾好奇过,如今安卓系统究竟是什么模样?在这个科技飞速发展的时代,操作系统如同人体的...
安卓6.0系统比5.0,从5.... 你有没有发现,自从手机更新了安卓6.0系统,感觉整个人都清爽了不少呢?没错,今天咱们就来聊聊这个话题...
安卓2.36系统升级,功能革新... 你知道吗?最近安卓系统又来了一次大变身,那就是安卓2.36系统升级!这可不是一个小打小闹的更新,而是...
安卓系统源码怎么打开,并可能需... 你有没有想过,安卓系统的源码就像是一扇神秘的门,隐藏着无数的技术秘密?想要打开这扇门,你得掌握一些小...
安卓8.0系统体验视频,智能革... 你有没有听说安卓8.0系统最近可是火得一塌糊涂啊!作为一个紧跟科技潮流的数码达人,我当然要来给你好好...
宣传系统漫画app安卓,探索安... 亲爱的读者们,你是否曾在某个午后,百无聊赖地打开手机,想要寻找一些轻松愉悦的读物?今天,我要给你介绍...
鸿蒙替换安卓系统吗,开启智能生... 你知道吗?最近科技圈里可是炸开了锅,因为华为的新操作系统鸿蒙系统,据说要大举进军手机市场,替换掉安卓...
手机安卓系统深度清理,解锁手机... 手机里的东西是不是越来越多,感觉就像一个装满了杂物的储物柜?别急,今天就来教你一招——手机安卓系统深...
安卓上的windows系统,融... 你有没有想过,在安卓手机上也能体验到Windows系统的魅力呢?没错,这就是今天我要跟你分享的神奇故...
安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...