专栏首页java思维导图经典面试问题: Top K 之 -- 海量数据找出现次数最多或,不重复的

经典面试问题: Top K 之 -- 海量数据找出现次数最多或,不重复的

林冠宏 / 指尖下的幽灵

仅列举一些解决方法,事实的解决方案是非常多的。

这些问题都是面临着有如下的考虑:

  • 内存不足以放下所有的数。
  • 机器CPU的核数不够。
  • ...

问这些问题的意义:

如果能把这些问题答好,必然是综合计算机各方面的知识,从内存到数据结构甚至还涉及到硬件,方法面面。至此,我给它定位是,综合考量一个程序员计算机基础能力的面试题。

一,找出不重复的

2.5亿正整数中找出不重复的整数。

思路一:

分治法 + HashMap (HashMap 不要局限在 Java 语言)

将 2.5 亿个整数,分批操作,例如分成 250 万一批,共100批次。每批使用循环遍历一次,存入 HashMap<int1,int2> 里面,int1 对应这个数,int2 对应它出现的次数,没出现就默认是 1 次。每操作完一批,就进行当前的 HashMap去重操作,读出 int2 > 1 的,排除掉。接下来的批次,以此类推,得出 100,剩下的自然就是不重复的。

好了,我们现在来计算下上面这个方案的双间复杂度,时间 & 空间

时间复杂度250W * 100轮 + 其它批次。对于多核机器,可以启动线程操作。

空间复杂度:使用 int 来进行存每一个数,保证不溢出情况下,那么就是 --> Key + Value : (250W * 4字节,4Byte)/(1024*1024) ~ (Key + 9.5MB) 内存。

思路二:

位图法 Bitmap(一个 bit 仅会是 0 或 1)

对于此题,我们可以设计每两个 bit 位,标示一个数的出现情况。00表示没有出现,01表示出现一次,10表示出现多次。2.5 亿个正整数,首先我们要知道是正整数,我们就不需要考虑负数,也就是无符号,无符号的整形占四个字节

我们以这个为例子,开始计算位图内存。

1B = 8b,4B = 32b,它可以表示的最大的整数是 2^32-1(不溢出),也就是说,我们需要 2^32-1 ~ 2^32来表示这2.5亿个数。我们上面说了,每个状态是两个,那么总共就是2^32*2个位。

那么我们可以一次申请的 位图 内存是:2^32*2 bit ,(2^32*2)/(1024*1024*8) = 1GB 即可。当然,我们也可以加上分治的思路,分批处理,不用直接用 1G,哈哈。

那么这样做的情况下怎样找到这个数呢?我举个例子,例如我们此时读入一个数是:6464对应的所在bit位是:64*2=128,也就是说第 127128 位共同标示了它的出现状态。其他的以此类推。每当我们读出一个数,我们就这样去找到它对应的bit位,先读出bit位的值,再做记录,已经是01的,再次来到,那么就应该修改为10。最后的我们这样得出结果:扫描整个位图,如果是10的,就下标/2得出这个数。

二,找出出现次数最多的

第一题:找出一篇文章中,出现次数最多的单词。

第二题:10亿个正整数找出重复次数最多的100个整数。

思路一:

分治法 + HashMap

没错,分治法 + HashMap 这个方法就是可以用来处理很多 Top K问题的。

对于问题一,其实比较简单,这道题也是我 2016 年腾讯第三轮技术面要求当场写代码的题目。我们可以先判断,这篇文章可能很长,也可能很短,那么我们应该规定一个字数的标志,作为一批的字数限制,例如100个文字。每100个文字是一批的处理极限,我们先读出100个,100以内的就直接全部读出。读出后,打散成字符串,例如英语文章它以空格和一些符号分割。使用split方法就可以打散。此时我们得出一个字符串数组String[] array,有了这个之后就可以参考 找出不重复 问题的解法。每批使用循环遍历一次,存入 HashMap<String,Integer> 里面,string 对应这个数的字符串,Integer 对应它出现的次数,最后最大的自然就是出现次数最多的。下面直接给出个 Demo 函数

第二题对应的 分治法 + HashMap

按照前面的案例,我们首先一样是要把这十亿个数分成很多份。例如 1000份,每份 10万。然后使用 HashMap<int,int> 来统计。在每一次的统计中,我们可以找出最大的100个数,为什么只找10万中的100个啊?因为我们有1000份,其它份里面的第二大可能是这份里最小的。这样全部加起来都100*1000个数了。OK,在我们找出这100*1000个侯选数后,继续分治处理,或者直接进行排序,如果直接排序就是10W个数。排序算法可以选快排等之类的,前100个就是结果。

思路二:

位图法 Bitmap

第一题,略。不是纯数字的,不建议采用位图法

第二题:

有了 找出不重复的 的例子做基础。我们此时直接知道这题的 正整数 最大也是只能到 2^23-1,对于这道题,我们不需要乘2,所以我们申请的内存大小也是512MB。这样我们就能使用这个位图把所有数都存进去。如果出现了一次,该bit位 = 1,没有就是0。多次出现的话,我们就不能累加到bit位里面了,因为它最大就是1。这时候我们会发现,出现多次的话,是无法通过bit位进行累加记录的。所以,此题也是不适合采用位图法

其他的

例如问:XXXXX中找出最大的一个,最小的一个,最大的几个,最小的几个。这类的就可以使用分治法+最小堆/最大堆秒之。

完矣

本文分享自微信公众号 - java思维导图(java-mindmap)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Spring Boot 这么火,常用注解和原理都给你整理好了!

    查看源码可发现,@SpringBootApplication是一个复合注解,包含了@SpringBootConfiguration,@EnableAutoCon...

    java思维导图
  • 程序员面试闪充——面试技巧

    面试,相亲,销售的过程都很类似,抽象一下,它们的本质是什么?我认为是:展示自我和挖掘对方需求的过程。 虽然说简历是工作的敲门砖,非常重要,但面试同样是决定你是否...

    java思维导图
  • 如何设计一个本地缓存

    最近在看 Mybatis 的源码,刚好看到缓存这一块,Mybatis 提供了一级缓存和二级缓存;一级缓存相对来说比较简单,功能比较齐全的是二级缓存,基本上满足了...

    java思维导图
  • Spring Job?Quartz?XXL-Job?年轻人才做选择,艿艿全莽~

    在产品的色彩斑斓的黑的需求中,有存在一类需求,是需要去定时执行的,此时就需要使用到定时任务。例如说,每分钟扫描超时支付的订单,每小时清理一次日志文件,每天统计前...

    芋道源码
  • 【模板小程序】求小于等于N范围内的质数

    关于搜寻一定范围内素数的算法及其复杂度分析                                                       ——曾晓...

    xiaoxi666
  • 利用easyui实现增删改查:easyui样式的日期的显示

    一天不写程序难受
  • Golang语言作为服务器,H5作为前端的视频传输

    demo下载地址: http://www.golangweb.com/forum.php?mod=viewthread&tid=2688&from=portal...

    李海彬
  • Google双因子认证python最好的

    py3study
  • SQL注入漏洞全接触--进阶篇

    其次,根据注入参数类型,在脑海中重构SQL语句的原貌,按参数类型主要分为下面三种:

    徐大嘴
  • Go 堆栈的理解

    堆:堆可以被看成是一棵树,如:堆排序。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,...

    孤烟

扫码关注云+社区

领取腾讯云代金券