1396. 设计地铁系统
题目描述
地铁系统跟踪不同车站之间的乘客出行时间,并使用这一数据来计算从一站到另一站的平均时间。
实现 UndergroundSystem
类:
void checkIn(int id, string stationName, int t)
- 通行卡 ID 等于
id
的乘客,在时间t
,从stationName
站进入 - 乘客一次只能从一个站进入
- 通行卡 ID 等于
void checkOut(int id, string stationName, int t)
- 通行卡 ID 等于
id
的乘客,在时间t
,从stationName
站离开
- 通行卡 ID 等于
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] 解释 UndergroundSystem undergroundSystem = new UndergroundSystem(); undergroundSystem.checkIn(45, "Leyton", 3); undergroundSystem.checkIn(32, "Paradise", 8); undergroundSystem.checkIn(27, "Leyton", 10); undergroundSystem.checkOut(45, "Waterloo", 15); // 乘客 45 "Leyton" -> "Waterloo" ,用时 15-3 = 12 undergroundSystem.checkOut(27, "Waterloo", 20); // 乘客 27 "Leyton" -> "Waterloo" ,用时 20-10 = 10 undergroundSystem.checkOut(32, "Cambridge", 22); // 乘客 32 "Paradise" -> "Cambridge" ,用时 22-8 = 14 undergroundSystem.getAverageTime("Paradise", "Cambridge"); // 返回 14.00000 。只有一个 "Paradise" -> "Cambridge" 的行程,(14) / 1 = 14 undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 11.00000 。有两个 "Leyton" -> "Waterloo" 的行程,(10 + 12) / 2 = 11 undergroundSystem.checkIn(10, "Leyton", 24); undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 11.00000 undergroundSystem.checkOut(10, "Waterloo", 38); // 乘客 10 "Leyton" -> "Waterloo" ,用时 38-24 = 14 undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 12.00000 。有三个 "Leyton" -> "Waterloo" 的行程,(10 + 12 + 14) / 3 = 12
示例 2:
输入 ["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"] [[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]] 输出 [null,null,null,5.00000,null,null,5.50000,null,null,6.66667] 解释 UndergroundSystem undergroundSystem = new UndergroundSystem(); undergroundSystem.checkIn(10, "Leyton", 3); undergroundSystem.checkOut(10, "Paradise", 8); // 乘客 10 "Leyton" -> "Paradise" ,用时 8-3 = 5 undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 5.00000 ,(5) / 1 = 5 undergroundSystem.checkIn(5, "Leyton", 10); undergroundSystem.checkOut(5, "Paradise", 16); // 乘客 5 "Leyton" -> "Paradise" ,用时 16-10 = 6 undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 5.50000 ,(5 + 6) / 2 = 5.5 undergroundSystem.checkIn(2, "Leyton", 21); undergroundSystem.checkOut(2, "Paradise", 30); // 乘客 2 "Leyton" -> "Paradise" ,用时 30-21 = 9 undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 6.66667 ,(5 + 6 + 9) / 3 = 6.66667
提示:
1 <= id, t <= 106
1 <= stationName.length, startStation.length, endStation.length <= 10
次- 所有字符串由大小写英文字母与数字组成
- 总共最多调用
checkIn
、checkOut
和getAverageTime
方法2 * 104
- 与标准答案误差在
10-5
以内的结果都被视为正确结果
解法
方法一:哈希表
我们用两个哈希表来存储数据,其中:
ts
:存储乘客的 id 和乘客的进站时间和进站站点。其中键为乘客的 id,值为元组(t, stationName)
。d
:存储乘客的进站站点和出站站点,以及乘客的行程时间和行程次数。其中键为元组(startStation, endStation)
,值为元组(totalTime, count)
。
当乘客进站时,我们将乘客的 id 和进站时间和进站站点存入 ts
中,即 ts[id] = (t, stationName)
。
当乘客出站时,我们从 ts
中取出乘客的进站时间和进站站点 (t0, station)
,然后计算乘客的行程时间 $t - t_0$,并将乘客的行程时间和行程次数存入 d
中。
当我们要求某个乘客的平均行程时间时,我们从 d
中取出乘客的行程时间和行程次数 (totalTime, count)
,然后计算平均行程时间 $totalTime / count$ 即可。
时间复杂度 $O(1)$,空间复杂度 $O(n)$。其中 $n$ 为乘客的数量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
|