如何实现从ArrayList衍生的公交站点对应线路的HashMap方法？

核心思路 #

要完成这个方法，你需要反向构建映射关系：从现有的routes（公交号→站点列表）出发，遍历每一条线路的所有站点，将每个站点与对应的公交号关联起来，最终得到站点→公交号集合的HashMap。

高效实现方案 #

直接遍历routes中的每一条线路和站点，避免重复遍历，效率更高：

public HashMap<String, HashSet<Integer>> getStopsAndBusNumbers() {
    HashMap<String, HashSet<Integer>> map = new HashMap<>();
    
    // 遍历每一条公交线路的键值对
    for (Map.Entry<Integer, ArrayList<String>> routeEntry : routes.entrySet()) {
        int busNumber = routeEntry.getKey();
        ArrayList<String> stopsOfRoute = routeEntry.getValue();
        
        // 遍历当前线路的所有站点
        for (String stop : stopsOfRoute) {
            // 如果站点未在结果Map中，先初始化对应的HashSet
            if (!map.containsKey(stop)) {
                map.put(stop, new HashSet<>());
            }
            // 将当前公交号添加到该站点的集合中
            map.get(stop).add(busNumber);
        }
    }
    
    return map;
}

复用已有方法的方案 #

如果你想复用已经实现的getBusesStoppingHere方法，可以先收集所有不重复的站点，再逐个调用方法填充结果：

public HashMap<String, HashSet<Integer>> getStopsAndBusNumbers() {
    HashMap<String, HashSet<Integer>> map = new HashMap<>();
    HashSet<String> allUniqueStops = new HashSet<>();
    
    // 先收集所有不重复的站点
    for (ArrayList<String> stops : routes.values()) {
        allUniqueStops.addAll(stops);
    }
    
    // 遍历每个站点，调用已有方法获取对应公交号集合
    for (String stop : allUniqueStops) {
        map.put(stop, getBusesStoppingHere(stop));
    }
    
    return map;
}

方案对比 #

• 第一种方案仅需两次嵌套遍历（线路→站点），时间复杂度为O(N)（N为所有站点的总数），效率更高。
• 第二种方案会对每个站点重新遍历所有线路，时间复杂度为O(M*K)（M为站点数，K为线路数），适合快速复用已有代码，但效率较低。

内容的提问来源于stack exchange，提问作者Harry