2.9 如何從給定的車票中找出旅程

【出自YMX面試題】

難度系數：★★★☆☆

被考察系數：★★★★☆

題目描述：

給定一趟旅途旅程中所有的車票信息，根據這個車票信息找出這趟旅程的路線。例如，給定下面的車票：（“西安”到“成都”），（“北京”到“上海”），（“大連”到“西安”），（“上海”到“大連”）。那么可以得到旅程路線為：北京→上海，上海→大連，大連→西安，西安→成都。假定給定的車票不會有環，也就是說，有一個城市只作為終點而不會作為起點。

分析與解答：

對于這種題目，一般而言可以使用拓撲排序進行解答。根據車票信息構建一個圖，然后找出這張圖的拓撲排序序列，這個序列就是旅程的路線。但這種方法的效率不高，它的時間復雜度為O（N）。這里重點介紹另外一種更加簡單的方法：Hash法。主要思路：根據車票信息構建一個HashMap，然后從這個HashMap中找到整個旅程的起點，接著就可以從起點出發依次找到下一站，進而知道終點。具體的實現思路為：

1）根據車票的出發地與目的地構建HashMap。

2）構建Tickets的逆向hashmap如下（將旅程的起始點反向）：

3）遍歷Tickets，對于遍歷到的key值，判斷這個值是否在ReverseTickets中的key中存在，如果不存在，那么說明遍歷到的Tickets中的key值就是旅途的起點。例如，“北京”在ReverseTickets的key中不存在，因此“北京”就是旅途的起點。實現代碼如下：

程序的運行結果為

算法性能分析：

這種方法的時間復雜度為O（N），空間復雜度也為O（N）。