题目描述

请你实现一个类 UndergroundSystem ，它支持以下 3 种方法：

1. checkIn(int id, string stationName, int t)

• 编号为 id 的乘客在 t 时刻进入地铁站 stationName 。
• 一个乘客在同一时间只能在一个地铁站进入或者离开。

2. checkOut(int id, string stationName, int t)

• 编号为 id 的乘客在 t 时刻离开地铁站 stationName 。

3. getAverageTime(string startStation, string endStation) 

• 返回从地铁站 startStation 到地铁站 endStation的平均花费时间。
• 平均时间计算的行程包括当前为止所有从 startStation 直接到达 endStation 的行程。
• 调用 getAverageTime 时，询问的路线至少包含一趟行程。

你可以假设所有对 checkIn 和 checkOut 的调用都是符合逻辑的。也就是说，如果一个顾客在 t1 时刻到达某个地铁站，那么他离开的时间 t2 一定满足 t2 > t1 。所有的事件都按时间顺序给出。

样例

输入：
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

输出：
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

解释：
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // 返回 14.0。从 "Paradise"（时刻 8）到 "Cambridge"(时刻 22)的行程只有一趟
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // 返回 11.0。总共有 2 躺从 "Leyton" 到 "Waterloo" 的行程，编号为 id=45 的乘客出发于 time=3 到达于 time=15，编号为 id=27 的乘客于 time=10 出发于 time=20 到达。所以平均时间为 ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // 返回 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // 返回 12.0

算法分析

1、记录每个人进入地铁站
2、记录每个人什么时候进入地铁站
3、用A@B表示从A城市到B城市，记录所有从A城市到B城市所有人的总时间
4、记录所有从A城市到B城市的总人数

• 进站时，记录这个人进入的地铁站以及时间
• 出站时，算出这个人这趟旅行的时间，加入到当前A城市到B城市的总时间，并加入到A城市到B城市的总人数
• 查询时，用A城市到B城市的总时间 / 总人数

时间复杂度$O(1)$

Java 代码

import java.util.HashMap;
import java.util.Map;

class UndergroundSystem {
    static Map<Integer,String> in = new HashMap<Integer,String>();//标记哪个人进入什么地铁站
    static Map<Integer,Integer> inTime = new HashMap<Integer,Integer>();//标记哪个人什么时候进入地铁站
    static Map<String,Integer> allTime = new HashMap<String,Integer>();//String记录的是A城市到B城市，映射所有人出总时间
    static Map<String,Integer> allCount = new HashMap<String,Integer>();//String记录的是A城市到B城市，映射出总人数
    public UndergroundSystem() {
        in.clear();
        inTime.clear();
        allTime.clear();
        allCount.clear();
    }

    public void checkIn(int id, String stationName, int t) {
        in.put(id, stationName);
        inTime.put(id, t);
    }

    public void checkOut(int id, String stationName, int t) {
        int startTime = inTime.get(id);//找到当前这个人进站的时间
        String startStation = in.get(id);//找到当前这个人进站的地址
        String trip = startStation + "@" + stationName;
        allTime.put(trip, allTime.getOrDefault(trip, 0) + t - startTime);
        allCount.put(trip, allCount.getOrDefault(trip, 0) + 1);
    }

    public double getAverageTime(String startStation, String endStation) {
        String trip = startStation + "@" + endStation;
        int time = allTime.get(trip);
        int count = allCount.get(trip);
        return (double)time / count;
    }
}

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem obj = new UndergroundSystem();
 * obj.checkIn(id,stationName,t);
 * obj.checkOut(id,stationName,t);
 * double param_3 = obj.getAverageTime(startStation,endStation);
 */