1396. 设计地铁系统

Medium

题目描述

地铁系统需要跟踪客户在不同站点间的出行时间，并用这些数据计算从一个站点到另一个站点的平均出行时间。

实现 UndergroundSystem 类：

void checkIn(int id, string stationName, int t)
- ID 为 id 的客户在时间 t 进入站点 stationName
- 一个客户在同一时间只能在一个地方签到
void checkOut(int id, string stationName, int t)
- ID 为 id 的客户在时间 t 从站点 stationName 退出
double getAverageTime(string startStation, string endStation)
- 返回从 startStation 到 endStation 的平均出行时间
- 平均时间是从所有之前直接从 startStation 到 endStation 的出行时间计算的（即在 startStation 签到然后在 endStation 退出）
- 从 startStation 到 endStation 的时间可能与从 endStation 到 startStation 的时间不同
- 在调用 getAverageTime 之前，至少有一个客户从 startStation 出行到 endStation

你可以假设所有对 checkIn 和 checkOut 方法的调用都是一致的。如果客户在时间 t1 签到然后在时间 t2 退出，那么 t1 < t2。所有事件都按时间顺序发生。

示例 1：

输入
["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.00000,11.00000,null,11.00000,null,12.00000]

约束条件：

1 <= id, t <= 10^6
1 <= stationName.length, startStation.length, endStation.length <= 10
所有字符串由大小写英文字母和数字组成
checkIn、checkOut 和 getAverageTime 的调用次数总共最多 2 * 10^4 次
与实际值的误差在 10^-5 以内的答案将被接受

解题思路

这道题需要设计一个地铁系统来追踪乘客的出行记录并计算平均时间。核心思路是使用哈希表来存储相关信息。

解题思路：

我们需要维护两个主要的数据结构：

签到记录表：记录每个乘客的签到信息（站点名和时间）
路线统计表：记录每条路线的总时间和次数，用于计算平均值

具体实现：

checkIn：将乘客的签到信息（站点和时间）存入签到记录表
checkOut：从签到记录表中获取该乘客的签到信息，计算出行时间，更新路线统计表，然后删除签到记录
getAverageTime：从路线统计表中获取总时间和次数，计算并返回平均时间

关键优化点：

使用字符串拼接作为路线的键值（如"起点->终点"），确保方向性
路线统计表存储{总时间, 次数}对，避免存储所有单次时间节省空间
签到记录在退出时立即删除，保持内存效率

这种设计保证了所有操作的时间复杂度都是O(1)，空间复杂度与活跃乘客数和不同路线数成正比。

代码实现

class UndergroundSystem {
private:
    unordered_map<int, pair<string, int>> checkInMap;  // id -> {stationName, time}
    unordered_map<string, pair<int, int>> routeMap;    // route -> {totalTime, count}
    
public:
    UndergroundSystem() {
        
    }
    
    void checkIn(int id, string stationName, int t) {
        checkInMap[id] = {stationName, t};
    }
    
    void checkOut(int id, string stationName, int t) {
        auto checkInInfo = checkInMap[id];
        checkInMap.erase(id);
        
        string route = checkInInfo.first + "->" + stationName;
        int travelTime = t - checkInInfo.second;
        
        routeMap[route].first += travelTime;
        routeMap[route].second += 1;
    }
    
    double getAverageTime(string startStation, string endStation) {
        string route = startStation + "->" + endStation;
        auto routeInfo = routeMap[route];
        return (double)routeInfo.first / routeInfo.second;
    }
};

class UndergroundSystem:

    def __init__(self):
        self.check_in_map = {}  # id -> (station_name, time)
        self.route_map = {}     # route -> [total_time, count]

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.check_in_map[id] = (stationName, t)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        start_station, start_time = self.check_in_map.pop(id)
        
        route = f"{start_station}->{stationName}"
        travel_time = t - start_time
        
        if route not in self.route_map:
            self.route_map[route] = [0, 0]
        
        self.route_map[route][0] += travel_time
        self.route_map[route][1] += 1

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        route = f"{startStation}->{endStation}"
        total_time, count = self.route_map[route]
        return total_time / count

public class UndergroundSystem {
    private Dictionary<int, (string station, int time)> checkInMap;
    private Dictionary<string, (int totalTime, int count)> routeMap;

    public UndergroundSystem() {
        checkInMap = new Dictionary<int, (string, int)>();
        routeMap = new Dictionary<string, (int, int)>();
    }
    
    public void CheckIn(int id, string stationName, int t) {
        checkInMap[id] = (stationName, t);
    }
    
    public void CheckOut(int id, string stationName, int t) {
        var checkInInfo = checkInMap[id];
        checkInMap.Remove(id);
        
        string route = $"{checkInInfo.station}->{stationName}";
        int travelTime = t - checkInInfo.time;
        
        if (!routeMap.ContainsKey(route)) {
            routeMap[route] = (0, 0);
        }
        
        routeMap[route] = (routeMap[route].totalTime + travelTime, routeMap[route].count + 1);
    }
    
    public double GetAverageTime(string startStation, string endStation) {
        string route = $"{startStation}->{endStation}";
        var routeInfo = routeMap[route];
        return (double)routeInfo.totalTime / routeInfo.count;
    }
}

var UndergroundSystem = function() {
    this.checkInMap = new Map();  // id -> {station, time}
    this.routeMap = new Map();    // route -> {totalTime, count}
};

UndergroundSystem.prototype.checkIn = function(id, stationName, t) {
    this.checkInMap.set(id, {station: stationName, time: t});
};

UndergroundSystem.prototype.checkOut = function(id, stationName, t) {
    const checkInInfo = this.checkInMap.get(id);
    this.checkInMap.delete(id);
    
    const route = `${checkInInfo.station}->${stationName}`;
    const travelTime = t - checkInInfo.time;
    
    if (!this.routeMap.has(route)) {
        this.routeMap.set(route, {totalTime: 0, count: 0});
    }
    
    const routeInfo = this.routeMap.get(route);
    routeInfo.totalTime += travelTime;
    routeInfo.count += 1;
};

UndergroundSystem.prototype.getAverageTime = function(startStation, endStation) {
    const route = `${startStation}->${endStation}`;
    const routeInfo = this.routeMap.get(route);
    return routeInfo.totalTime / routeInfo.count;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
checkIn	O(1)	O(1)
checkOut	O(1)	O(1)
getAverageTime	O(1)	O(1)
总体空间复杂度	-	O(P + S)

其中 P 是同时在系统中的乘客数量，S 是不同路线的数量。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目