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