Kotlin程序员：高效找出旅程的车票算法

【出自YMX面试题】

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

题目描述：

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

分析与解答：

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

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

Tickets={（“西安”到“成都”），（“北京”到“上海”），（“大连”到“西安”），（“上海”到“大连”）}(www.xing528.com)

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

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

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

程序的运行结果如下：

北京-＞上海，北京-＞大连，大连-＞西安，西安-＞成都

算法性能分析：

这种方法的时间复杂度为O（N），空间复杂度也为O（N）。