笔试算法模拟题精解之“超车”-阿里云开发者社区

开发者社区> 算法编程> 正文

笔试算法模拟题精解之“超车”

简介: 只要超过了一辆车,就算发生了超车,按照此思路批量判断超车,提高内循环的效率。

【在线编程产品介绍】

阿里云开发者社区在线编程:

免费刷题大神器,助你拿到好offer

周赛月赛不停歇,做题还能领奖品

大赛笔试全真题,常做常新有惊喜

点击链接开始产品体验:https://developer.aliyun.com/coding

本文为大家介绍的是“47.超车”的解法探究。先来看一下题目内容:

题目详情

查看题目:超车一天某地在举行公路自行车比赛,一共有n名选手参加(2<=n<=100000),在比赛的过程中,有一段路程观众是看不见的,现在给你了选手进入这段路程的顺序编号,又给了选手出这段路程的顺序编号(顺序按照先进先出的原则,编号为1-n),请你计算一下,有多少名选手在这段公路上完成了超车(出路段后超过了进路段前在自己前面的选手)。
第一行输入一个数n,第二行输入n个数,表示选手进入路段的顺序,第三行输入n个数,表示选手出路段时的顺序输出一个数s,表示有s名选手在该路段中超车

示例1
输入:
5
[4,2,1,3,5]
[2,4,1,5,3]
输出:
2
注意
输入样例表示4第一个进,2第二个进....然后2第一个出,4第二个出...

解题思路详解

方法 1:暴力解法(不能通过)

根据题意,超车意味着对于入洞前序列中的每辆车x及x前面的车集合{a,b,c,d...},如果在出洞序列中,发现x前面的某车,出洞时不在{a,b,c,d...}集合中,就说明x超过了这辆不在{a,b,c,d...}集合中的车。而且这个超车行为与其他车无关,也就是说,即使上面个的清空中x的排名后撤了,被其它车超过了,它也依然被视为发生了超车。“只要超过了一辆车,就算发生了超车”

根据上面思路,首先需要遍历入洞序列,对每辆车x遍历,同时用一个列表记录下入洞序列中x前面的车。对这样的x和列表,再去出洞序列中从尾部开始遍历,直到发现x停止。如果遍历出洞序列的过程中,发现某车存在于列表中,说明这辆车入洞前在x的前面且出洞后在x的后面,发生了超车,此时令结果加1。

如果简单应用这种代码,不加优化,会有嵌套循环,时间复杂度很高,不能通过。

时间复杂度:O(n^2)

空间复杂度:O(1)

方法 2:批量判断超车,提高内循环的效率

上面的思路中,耗时最多的部分,就是内循环在出洞序列中,判断“入洞序列在x前面车的集合”,有没有出现在x的后面这个步骤。如果直接查找,由于出洞序列没有顺序,不可以使用二分查找,只能从挨个线性搜索出洞序列数组,时间复杂度非常高。所以我们先从这里切入,尝试优化。

根据上面的定义,我们想,既然x只要超过入洞序列中,x前面的任何一辆车就算超车,而且题目不要求我们求出超过了哪辆车,也不要求求出超过了几辆车,那么我们可不可以将超过一辆车的行为,视为x超过了入洞序列x前面所有车组成的车队的行为呢?

首先我们需要用哈希表(或者表示入洞出洞顺序的数组),记录下每辆车出洞和入洞排名的对应关系;之后从0(或者说1)开始遍历入洞排名,找到入洞序列中排名i-1及i-1之前的车组成的 “车队”,在出洞序列中覆盖的范围,你不需要记录这个范围中具体覆盖了那些车,只需要记录这个范围的第一辆车a和最后一辆车z。最后,判断i车在出洞时的位置x,是否超过了这个车队的最后一辆车的位置z。如果超过了,说明发生了超车,如果未超过,说明可以把i车也加入到车队中,将车队的最后一辆车位置更新为x。然后继续这个遍历过程,就可以得到结果:
image.png
这种解法利用了哈希表查找速度,编写合理的话,时间复杂度会比较低。

时间复杂度:O(n)
空间复杂度:O(2n)

看完之后是不是有了答题思路了呢,快来练练手吧:47.超车

在线编程周赛、月赛火热进行中,更有限时答题活动,社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情:在线编程内测中,抢先周赛赢好礼!面试考试前,快来刷刷题!

APPbanner784-312.png

上一篇: 笔试算法模拟题精解之“ 最优分组”
下一篇:笔试算法模拟题精解之“Alice的01串”的三种解法

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
官网链接