2.9 如何从给定的车票中找出旅程的路线

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

给定一趟旅途旅程中所有的车票信息，要求根据这个车票信息找出这趟旅程的路线。例如：给定下面的车票：（“西安”到“成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）。那么可以得到旅程路线为：北京-＞上海，上海-＞大连，大连-＞西安，西安-＞成都。假定给定的车票不会有环，也就是说，有一个城市只作为终点而不会作为起点。

分析与解答：

对于这种题目，一般而言可以使用拓扑排序进行解答。首先根据车票信息构建一个图，然后找出这张图的拓扑排序序列，这个序列就是旅程的路线。但这种算法的效率不高，它的时间复杂度为O（n）。这里重点介绍另外一种更加简单的方法：Hash法。hash法的主要思路为根据车票信息构建一个HashMap，然后从这个HashMap中找到整个旅程的起点，接着就可以从起点出发依次找到下一站，进而知道终点。具体的实现思路为：

1）根据车票的出发地与目的地构建HashMap。

Tickets={（“西安”到成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）}

2）构建Tickets的逆向Hashmap如下（将旅程的起始点反向）：

ReverseTickets={（“成都”到“西安”），（“上海”到“北京”），（“西安”到“大连”），（“大连”到“上海”）}

3）遍历Tickets，对于遍历到的key值，判断这个值是否在ReverseTickets中的key中存在，如果不存在，那么说明遍历到的Tickets中的key值就是旅途的起点。例如：“北京”在ReverseTickets的key中不存在，因此“北京”就是旅途的起点。实现代码如下：

程序的运行结果为

算法性能分析：

这个算法的时间复杂度为O（n），空间复杂度也为O（n）。