2021-10-02 [Mnsx

给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。

根据题目信息，可知在List容器中，第一位的数据是起点站，第二位是终点站，可以从起点站道终点站，最终需要求得的数据是无法作为起点站的终点站，那么重点在于求出只在List的第二位中出现的数据。

初次看完这道题的题目，我最开始的思路是使用HashMap来存储String数据出现的次数，在第一位出现就减一，第二位出现就加一，没出现过就设置为零，那么最终会出现，最开始的起点站为-1，其他的数据为0，所需要的最终终点站为1，那么遍历HashMap返回value为1的值即可。

class Solution {
    public String destCity(List> paths) {
	//实例化HashMap
        Map hash = new HashMap();
	//遍历，将在第一位出现的数据的value加一，将第二位出现的数据的value减一，如果未出现过，那么将value设为0再进行
        for(List lists : paths){
            hash.put(lists.get(0), hash.getOrDefault(lists.get(0), 0) - 1);
            hash.put(lists.get(1), hash.getOrDefault(lists.get(1), 0) + 1);
        }
	//遍历HashMap将value=1的值返回
        for(Map.Entry entry : hash.entrySet()){
            if(entry.getValue() >= 1){
                return entry.getKey();
            }
        }
        return null;
    }
}

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

由于第一种思路时间为4ms，让我考虑可能使用HashMap会导致一些重复的工作，所以我选择使用HashSet来减少value取零时遍历的时间损耗，主要思路是将第一位的数据全部装进HashSet中，再使用第二位的数据进行判断，最终的终点站应该不会出现在第一位的数据中，返回不在HashSet中出现的。

class Solution {
    public String destCity(List> paths) {
	//实例化HashSet
        Set set = new HashSet();
	//遍历将第一位存入HashSet中
        for(List list : paths){
            set.add(list.get(0));
        }
	//返回HashSet中未出现的数据
        for(List list : paths){
            if(!set.contains(list.get(1))){
                return list.get(1);
            }
        }
        return null;
    }
}

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