题目链接

题目描述

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

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

思路一：

通过观察可知终点有一个特点，就是出现[x,y]中的后一位且只出现一次，故我们可以利用hashmap给他们做一个词频统计，但是不同的是，假设这个单词出现在数组的第0位，则加上1，若出现是在后一位则加上-1.最后我们只需要遍历一遍该hashmap，找到值为-1，将其键名输出即可。

代码实现

class Solution {
    public String destCity(List<List<String>> paths) {
        HashMap<String, Integer> sites = new HashMap<String, Integer>();
        for(int i=0;i<paths.size();i++){
            if(sites.get(paths.get(i).get(0)) != null){
                sites.put(paths.get(i).get(0),sites.get(paths.get(i).get(0))+1);
            }else{
                sites.put(paths.get(i).get(0),1);
            }
            if(sites.get(paths.get(i).get(1)) != null){
                sites.put(paths.get(i).get(1),sites.get(paths.get(i).get(1))-1);
            }else{
                sites.put(paths.get(i).get(1),-1);
            }
        }
        for (String i : sites.keySet()) {
            if(sites.get(i) == -1) return i;
        }
        return "";

    }
}

时间复杂度: O(n)

空间复杂度: O(n)

思路二：

采用暴力枚举的方式求解，每次用数组中的最后一个元素去与其他数组中的第一个元素进行检查，若发现有相同的元素则跳出，进入下一个循环，若无相同则输出结果。

代码实现

时间复杂度: O($n^2$)

空间复杂度: O(1)