【線上程式設計産品介紹】
阿裡雲開發者社群線上程式設計：
免費刷題大神器，助你拿到好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.超車線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：
線上程式設計内測中，搶先周賽赢好禮！面試考試前，快來刷刷題！
上一篇： 筆試算法模拟題精解之“ 最優分組” 下一篇： 筆試算法模拟題精解之“Alice的01串”的三種解法