【在线编程产品介绍】
阿里云开发者社区在线编程：
免费刷题大神器，助你拿到好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。然后继续这个遍历过程，就可以得到结果：
这种解法利用了哈希表查找速度，编写合理的话，时间复杂度会比较低。
时间复杂度：O(n)
空间复杂度：O(2n)
看完之后是不是有了答题思路了呢，快来练练手吧：47.超车
在线编程周赛、月赛火热进行中，更有限时答题活动，社区定制卫衣、双肩背包等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程内测中，抢先周赛赢好礼！面试考试前，快来刷刷题！