一些海量数据排序算法问题总结

亦凉 2023-07-12 08:42 1阅读 0赞

**1.给2000千万高考学生排序，要求要能根据分数找到该学生的排名？**

千万别被2000千万这个数字唬住，理性的看一下题，“高考”这个词不知道你注意到了没？这是一个隐藏条件。你高考考了多少分？

总分多少？可能有的小伙伴已经反应过来了。高考700分，那我们开一个700大小的数组，记录每个分数的的个数就可以了。

对，就是使用桶排序的算法，来进行排。

这一类题他虽然样子很吓人，但是仔细 发现他的范围很小，就抓住他这个范围小来做文章。

时间复杂度：n  空间复杂度也是700

**2.给2亿个不重复的正整数进行排序(范围0-2亿）？**

一个数比一个数夸张，刚才我们使用的桶排序，现在数的范围是很大的，所以我们应该想怎么把他存储起来，既能节省空间还快，主要是你怎么来存储，2亿个int类型，一个int4bit，也就是需要8亿bit(8亿bit大概等于800M,内存恐怕吃不消)。

此时有一个“不重复”这三个字就特别扎眼，我们怎么利用这个特性呢？

我们居然不能用一个int去装，那我们就可以用一位去装，int  = 4bit = 32位。

那么用的空间就是：2亿/32 （大概是25M）这下内存轻轻松松。

25M大概需要600万长度的数组。

做法详情x为待排序数字。 x/32找到数组下标。x%32找到它对应的位，然后把该位置为1。

这样就用奇技淫巧给解决掉了。

**3.给你一个超大的文件，找出出现频率最高的5个?**

这道题可能就没那个多的奇技淫巧了。

条件一个一个的增加，先是找出频率最高的5个，这个没有多余的话，肯定是根据频率最大堆排序。

那么一个超大文件，也就是说i我们内存没办法直接装下，可以将这个文件先分解（根据实际内存大小和文件大小判断，下边以5000份做例子），这时候我们把文件分成了5000份的小文件，然后我们为每个小文件构造一个数量为5的最大堆。其余的数字就可以清掉了。然后5000个小文件就行排序，这时候归并就要登场了。

我们通过归并然后对这5千个数据进行归并拿前5。这就找到了。

**4.一亿个int，short类型的数字进行排序？**

这个题是在字节二面的时候遇到的，这个题当时没有想出什么好的办法，然后面试官也没告诉我。

后来查了资料啥的，然后感觉也没有特别好的方法。

直接快排。

如果有大佬有更好的见解欢迎赐教！

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关关于海量数据查找排序问题

问题:假设一个文件中有9亿条不重复的9位整数，现在要求对这个文件进行排序。一般解题思路: 1、将数据导入到内存中 2、将数据进行排序　（比如插入排序、快速排

妖狐艹你老母/ 2023年10月17日 15:33/ 0 赞/ 130 阅读

相关海量数据排序

海量数据排序 1、外排序　　传统的排序算法一般指内排序算法，针对的是数据可以一次全部载入内存中的情况。但是面对海量数据，即数据不可能一次全部载入内存，需要

ゝ一纸荒年。/ 2023年08月17日 16:56/ 0 赞/ 49 阅读

相关一些海量数据排序算法问题总结

1.给2000千万高考学生排序，要求要能根据分数找到该学生的排名？千万别被2000千万这个数字唬住，理性的看一下题，“高考”这个词不知道你注意到了没？这是一个隐藏条件。你高

亦凉/ 2023年07月12日 08:42/ 0 赞/ 2 阅读

相关排序算法性能分析和海量数据排序问题

排序算法性能分析时间和空间复杂度快速排序的优化海量数据排序问题：时间和空间复杂度整理： <table> <thead> <

╰半夏微凉°/ 2022年11月17日 05:29/ 0 赞/ 153 阅读

相关海量数据处理算法（top K问题）

举例有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。思路首先把文件分开针对

Bertha 。/ 2022年09月26日 13:58/ 0 赞/ 152 阅读

相关海量数据问题

1. 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？方案1：　　可以估计每个文件安的大小为50G×6

偏执的太偏执、/ 2022年08月18日 02:48/ 0 赞/ 168 阅读

相关数据结构——排序算法总结

排序（Sorting）就是将一组对象按照规定的次序重新排列的过程，排序往往是为检索而服务的，它是数据处理中一种很重要也很常用的运算。例如我们日常学习中的查字典或者书籍的目录

淡淡的烟草味﹌/ 2022年08月10日 12:57/ 0 赞/ 192 阅读

相关海量数据分析问题总结

1）给⼀个超过100G⼤⼩的log file, log中存着IP地址, 设计[算法][Link 1]找到出现次数最多的IP地址？第一题：首先我们的思路就是利用哈希进

清疚/ 2022年07月12日 09:59/ 0 赞/ 247 阅读

相关海量数据处理算法总结

前面我们说海量数据处理提到，从算法的角度去考虑处理海量数据。 [1. Bloom Filter][] [【Bloom Filter】 ][1.

港控/mmm°/ 2022年06月05日 04:40/ 0 赞/ 313 阅读

相关海量数据处理:排序问题

一个文件中有9亿条不重复的9位整数,对这个文件中数字进行排序; 针对这个问题,最容易想到的方法是将所有数据导入到内存中,然后使用常规的排序方法,例如插入排序,快

╰+攻爆jí腚メ/ 2022年05月22日 05:19/ 0 赞/ 292 阅读