专栏首页Java后端技术栈【面试必备】如何在10亿数中找出前1000大的数?

【面试必备】如何在10亿数中找出前1000大的数?

小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

之前小史在BAT三家的面试中已经挂了两家,今天小史去了BAT中的最后一家面试了。

简单的自我介绍后,面试官给了小史一个问题。

【面试现场】

题目:如何在10亿数中找出前1000大的数?

小史:我可以用分治法,这有点类似快排中partition的操作。随机选一个数t,然后对整个数组进行partition,会得到两部分,前一部分的数都大于t,后一部分的数都小于t。

小史:如果说前一部分总数大于1000个,那就继续在前一部分进行partition寻找。如果前一部分的数小于1000个,那就在后一部分再进行partition,寻找剩下的数。

小史:首先,partition的过程,时间是o(n)。我们在进行第一次partition的时候需要花费n,第二次partition的时候,数据量减半了,所以只要花费n/2,同理第三次的时候只要花费n/4,以此类推。而n+n/2+n/4+...显然是小于2n的,所以这个方法的渐进时间只有o(n)

(注:这里的时间复杂度计算只是简化计算版,真正严谨的数学证明可以参考算法导论相关分析。)

半分钟过去了。

小史一时慌了神。

他回忆起了之前吕老师给他讲解bitmap时的一些细节。突然有了一个想法。

小史在纸上画了画。

理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:

TopN.java

Main.java

运行结果:

面试官看了一下。

小史熟练地介绍起了自己的项目,由于准备充分,小史聊起来游刃有余。面试官问的几个问题也进行了详细的解释。

小史走后,面试官在系统中写下了面试评语:

【遇见吕老师】

小史回到学校哼着歌走在校园的路上,正好碰到吕老师。

小史把面试情况和吕老师说了一下。

小史:感悟还挺深的。虽然平时做过topN的问题,知道分治法时间更少。但是碰到具体问题的时候还是要具体分析,这种大数据量的情况下反而用堆会更快。

本文分享自微信公众号 - Java后端技术(JavaITWork)

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 为什么越来越多的开发者选择使用Spring Boot

    使用Java做Web应用开发已经有近20年的历史了,从最初的Servlet1.0一步步演化到现在如此多的框架,库以及整个生态系统。经过这么长时间的发展,Java...

    Java后端技术
  • 程序员如何在百忙之中不走岔路,不白忙!

    程序员忙,似乎是个公论,有些程序员甚至会认为,不忙的程序员无法快速地进步,从而会落伍。或者说,不忙的程序员有可能被公司末尾淘汰掉。对此,一直危机感很重的我深以为...

    Java后端技术
  • 你的数据库密码还在裸奔吗?试一试Druid数据库密码加解密吧!

    1、替换DBCP和C3P0。Druid提供了一个高效、功能强大、可扩展性好的数据库连接池。

    Java后端技术
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    Java3y
  • BAT面试常爱问的MySQL数据库为何要用B+树存储索引,你真的懂吗?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    乔戈里
  • 【面试现场】为什么MySQL数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    帅地
  • 【面试现场】为什么 MySQL 数据库要用B+树存储索引?

    小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。

    五分钟学算法
  • 「PHP编程」PHP中的这些坑,PHP开发常见填坑备注

    在日常开发中,我们经常碰到这样的问题,即有些PHP问题看似简单,一说就明,但是一到使用时就踩坑。比如,下面我所列的几条:

    ZhangXianSheng
  • 一家年交易规模达30亿美元DSP公司

    如果你对DSP行业了解,单看年交易规模达到30亿美元,就应该知道是哪家了,毕竟有这么大交易流水的DSP是屈指可数的。

    GA小站
  • ddd

    dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

    用户4694318

扫码关注云+社区

领取腾讯云代金券