题目

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

来源：https://leetcode-cn.com/problems/destination-city

解题思路

遍历一次建立所有城市与出发城市的两个集合，两个集合做差即是终点城市

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def destCity(self, paths):
        """
        :type paths: List[List[str]]
        :rtype: str
        """
        allCity = set()
        beginCity = set()
        for path in paths:
            allCity.add(path[0])
            allCity.add(path[1])
            beginCity.add(path[0])
        return (allCity - beginCity).pop()

分析

空间复杂度：O(n)
时间复杂度：O(n)

和建立哈希表的方式相比，集合的方法更加快速，而且不会受到循环线路影响（当然题目已经排除这种可能）