栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法从入门到放弃——第十期 归并

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法从入门到放弃——第十期 归并

最近遇上一个某宇宙厂的面试题:

进程pid 进程开始时间 进程结束时间 cpu使用率

1          1:00                 2:00              10

2          1:20                 3:00              15

3          2:30                 4:00              30

题目类似这样,要你求cpu使用率最高的时间段

题目其实不难,想要实现有简单的方式,有难的方式。拿到之后总感觉两个字:做过

抽象之后大致就是一个有序数组的归并,类似 力扣88 这样的,

按理来说不是什么难问题,但是面试官让我所处思路和时间复杂度之后,我自己迟疑了:并不是最优,刷题的时候AC过了没思考最优解法,心中无墨水,有苦说不出。

在这把归并解决一下,实现先放一放,说说思路

归并的方式很多,最简单的两两归并,这当然不能算是多路归并

真正意义上的多路归并:

1、循环遍历找最小

就比如链表

1->2->3

2->3->5

2->2->4

循环取头就可以了,那么时间复杂度是遍历所有的元素,m*n

2、最小堆

建立最小堆,每次从中取最小即可,时间复杂度nlogn,这里我们也说过,取堆顶求最小,全塞入最小堆,求最大topk

3、胜者数

建立胜者树,每次取胜者就可以了,和最小堆一样

实现

//TODO,实现先放放,有时间写

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/733171.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号