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）。