上海装修公司排名榜十大品牌,宁波怎么优化seo关键词,做网站游戏推广赚钱吗,2024新冠会再次封城吗现在文章目录 前言对20GB文件进行排序超大文本中搜索两个单词的最短距离从10亿数字中寻找小于100万个数字总结 前言 提示#xff1a;你生命的前半辈子或许属于别人#xff0c;活在别人的认为里。那把后半辈子还给自己#xff0c;去追随你内在的声音。 --荣格 理解了前面的几个题… 文章目录 前言对20GB文件进行排序超大文本中搜索两个单词的最短距离从10亿数字中寻找小于100万个数字总结 前言 提示你生命的前半辈子或许属于别人活在别人的认为里。那把后半辈子还给自己去追随你内在的声音。 --荣格 理解了前面的几个题目知乎这里我们在看看在海量数据场景下的查询问题。 对20GB文件进行排序
题目要求假设你有一个20GB的文件每行一个字符串请说明如何对这个文件进行排序
分析这里给出的大小是20GB其实面试官在暗示我们不要将所有文件都装入内存里面因此我们只有将文件划分成块每块大小是xMBx就是可用的内存大小比如如果是1GB的块那么我们就可以将文件分成20块。我们先对每块进行排序然后再逐步合并。这时候我们可以使用两两并归也可以使用堆排序的策略将其逐步合并成一个相关的可以看以往章节介绍
这种排序方式也称为外部排序。
超大文本中搜索两个单词的最短距离
题目要求有一个超大文本文件内部是很多单词组成的现在给定两个单词请你找出这两个单词在这个文本中的最小距离。你有办法在O(n)时间里完成搜索吗方法的空间复杂度如何。
分析这个题目咋看起来含简单遍历一下找到两个单词的位置w1和w2然后比较一下就可以了然而这里的w1可能存在多个位置w2也一样。看下面的图 这个时候如何找到最小的距离呢
最直观的做法就是遍历数组words对数组中的每个word1遍历数组words找到每个word2并计算距离。该做法的最坏的时间复杂度为O(n^2)需要优化。
本题目少不了遍历一次数组找到所有word1和word2出现的位置但是为了方便比较我们可以将其放入一个数组中。比如
ListA:{1,2,3,5,9,34}
ListB:{4,8,12,56}
合并后
List:{1a,2a,3a,4b,5b,12b,34a,56b}合并成一个之后更方便查找的数组数字便是出现的位置后面的一个元素表示元素是什么然后一遍遍历一遍比较就可以了。
但是对于超大文本如果文本太大那么这个list可能会产生溢出还需要继续观察我们或发现其实不用单独构造list从左到右遍历数组words当遍历到word1时如果已经遍历的单词中存在word2为了方便记录最短距离应该取一个已经遍历到的word2所在的下标计算和当前下边的距离。同理当遍历到word2时应该取最后一个已经遍历到的word1所在的下标计算和当前下标的距离。
经过以上分析我们可以遍历一次数组就可以得到最短距离并且将复杂度降低到O(n)。用index1 和index2分别表示数组word已经遍历到单词的最后一个word1和word2下标。初始状态下index1和index2为-1.遍历数组word当遇到word2时执行以下操作
如果遇到word1则将index1更新为当前下标如果遇到word2则将index2更新为当前下标。如果index1和index2都非负则计算两个下标的距离|index1 - index 2|并用该距离更新最短距离。
遍历结束之后就可以获取word1和word2的最短距离。
进阶问题如果再寻找的过程中这个文件会重复多次而每次寻找的单词不同则可以维护一个哈希表记录每个短促的下标列表。遍历一次文件按照下标递增顺序得到每个单词再文件中出现的所有下标。寻找单词时只需要得到两个单词的下标列表。使用双指针遍历下标链表就可以得到两个单词的最短距离
从10亿数字中寻找小于100万个数字
题目要求设计一个算法给定一个10亿个数字找出最小的100万的数字。假定计算机内存足够容纳10亿个数字。
分析本题常见的做法有三种
先对元素排序然后去取出前100万个数字该方法的时间复杂度为O(nlogn)。很明显这样做时间和空间的消耗很大采用选择排序首先遍历10亿个数找最小然后再遍历一遍找第二小…直到找到100万个。这种方式的时间复杂度(nm)执行10亿*100万次。实现难度高采用大顶堆来解决。推荐算法通过村第十四关-堆|白银笔记|经典问题-CSDN博客 堆排序原理。
首先前提创建100万存储空间大顶堆最大元素位于堆顶。
然后遍历整个序列只要比堆顶元素小才可以放入堆中。并删除原堆的最大元素。之后继续遍历剩下的序列。直到最后剩下的之后100万个数字。
采用这一种遍历方式只需要遍历一次10亿个数字还可以接受。更新堆的代价是O(nlogn)也是勉强够用的。堆的占用空间是100万*4大约就是4MB的空间。也是不错的选择
如果数量没有这么大上面的其他方法也不是不可以。
如果将10亿数字换成数据流也可以采用堆的方式而且对数据流来说几乎能采用堆来做的。 总结
提示超大数据排序超大数据搜索问题海量数据集遍历超大规模数据流堆的排序原理 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
