文章目录
- 题目
-
- 标题和出处
- 难度
- 题目描述
-
- 要求
- 示例
- 数据范围
- 解法
-
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题：设计地铁系统
出处：1396. 设计地铁系统
难度
6 级
题目描述
要求
一个地铁系统正在收集乘客在不同站之间的花费时间。他们在使用这些数据计算从一个地铁站到另一个地铁站的平均花费时间。
实现
UndergroundSystem
texttt{UndergroundSystem}
UndergroundSystem 类：
-
void
checkIn(int
id,
string
stationName,
int
t)
texttt{void checkIn(int id, string stationName, int t)}
void checkIn(int id, string stationName, int t)- 卡号为
id
texttt{id}
id 的乘客在t
texttt{t}
t 时刻进入地铁站stationName
texttt{stationName}
stationName。 - 一个乘客在同一时间只能进入一个地点。
- 卡号为
-
void
checkOut(int
id,
string
stationName,
int
t)
texttt{void checkOut(int id, string stationName, int t)}
void checkOut(int id, string stationName, int t)- 卡号为
id
texttt{id}
id 的乘客在t
texttt{t}
t 时刻离开地铁站stationName
texttt{stationName}
stationName。
- 卡号为
-
double
getAverageTime(string
startStation,
string
endStation)
texttt{double getAverageTime(string startStation, string endStation)}
double getAverageTime(string startStation, string endStation)- 返回从地铁站
startStation
texttt{startStation}
startStation 到地铁站endStation
texttt{endStation}
endStation 的平均花费时间。 - 平均时间计算的行程包括当前为止所有从
startStation
texttt{startStation}
startStation 直接到达endStation
texttt{endStation}
endStation 的行程，即进入地铁站startStation
texttt{startStation}
startStation 之后离开地铁站endStation
texttt{endStation}
endStation。 - 从地铁站
startStation
texttt{startStation}
startStation 到地铁站endStation
texttt{endStation}
endStation 的花费时间可能不同于从地铁站endStation
texttt{endStation}
endStation 到地铁站startStation
texttt{startStation}
startStation 的花费时间。 - 调用
getAverageTime
texttt{getAverageTime}
getAverageTime 时，至少已经有一个乘客从地铁站startStation
texttt{startStation}
startStation 乘坐到地铁站endStation
texttt{endStation}
endStation。
- 返回从地铁站
你可以假设所有对
checkIn
texttt{checkIn}
checkIn 和
checkOut
texttt{checkOut}
checkOut 的调用都是符合逻辑的。如果一个乘客在
t
1
texttt{t}_texttt{1}
t1 时刻进入某个地铁站并在
t
2
texttt{t}_texttt{2}
t2 时刻离开某个地铁站，那么
t
1
t1t2。所有的事件都按时间顺序给出。
示例
示例 1：
输入：
[“UndergroundSystem”,”checkIn”,”checkIn”,”checkIn”,”checkOut”,”checkOut”,”checkOut”,”getAverageTime”,”getAverageTime”,”checkIn”,”getAverageTime”,”checkOut”,”getAverageTime”]
texttt{[“UndergroundSystem”,”checkIn”,”checkIn”,”checkIn”,”checkOut”,”checkOut”,”checkOut”,”getAverageTime”,”getAverageTime”,”checkIn”,”getAverageTime”,”checkOut”,”getAverageTime”]}
[“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”]]
texttt{[[],[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”]]}
[[],[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]
texttt{[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]}
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]
解释：
UndergroundSystem
undergroundSystem
=
new
UndergroundSystem();
texttt{UndergroundSystem undergroundSystem = new UndergroundSystem();}
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45,
“Leyton”,
3);
texttt{undergroundSystem.checkIn(45, “Leyton”, 3);}
undergroundSystem.checkIn(45, “Leyton”, 3);
undergroundSystem.checkIn(32,
“Paradise”,
8);
texttt{undergroundSystem.checkIn(32, “Paradise”, 8);}
undergroundSystem.checkIn(32, “Paradise”, 8);
undergroundSystem.checkIn(27,
“Leyton”,
10);
texttt{undergroundSystem.checkIn(27, “Leyton”, 10);}
undergroundSystem.checkIn(27, “Leyton”, 10);
undergroundSystem.checkOut(45,
“Waterloo”,
15);
texttt{undergroundSystem.checkOut(45, “Waterloo”, 15);}
undergroundSystem.checkOut(45, “Waterloo”, 15); // 乘客
45
texttt{45}
45 从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Waterloo”
texttt{“Waterloo”}
“Waterloo” 的时间是
15
–
3
=
12
texttt{15 – 3 = 12}
15 – 3 = 12
undergroundSystem.checkOut(27,
“Waterloo”,
20);
texttt{undergroundSystem.checkOut(27, “Waterloo”, 20);}
undergroundSystem.checkOut(27, “Waterloo”, 20); // 乘客
27
texttt{27}
27 从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Waterloo”
texttt{“Waterloo”}
“Waterloo” 的时间是
20
–
10
=
10
texttt{20 – 10 = 10}
20 – 10 = 10
undergroundSystem.checkOut(32,
“Cambridge”,
22);
texttt{undergroundSystem.checkOut(32, “Cambridge”, 22);}
undergroundSystem.checkOut(32, “Cambridge”, 22); // 乘客
32
texttt{32}
32 从
“Paradise”
texttt{“Paradise”}
“Paradise” 到
“Cambridge”
texttt{“Cambridge”}
“Cambridge” 的时间是
22
–
8
=
14
texttt{22 – 8 = 14}
22 – 8 = 14
undergroundSystem.getAverageTime(“Paradise”,
“Cambridge”);
texttt{undergroundSystem.getAverageTime(“Paradise”, “Cambridge”);}
undergroundSystem.getAverageTime(“Paradise”, “Cambridge”); // 返回
14.00000
texttt{14.00000}
14.00000。从
“Paradise”
texttt{“Paradise”}
“Paradise” 到
“Cambridge”
texttt{“Cambridge”}
“Cambridge” 的行程有
1
texttt{1}
1 个，
(14)
/
1
=
14
texttt{(14) / 1 = 14}
(14) / 1 = 14
undergroundSystem.getAverageTime(“Leyton”,
“Waterloo”);
texttt{undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);}
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”); // 返回
11.00000
texttt{11.00000}
11.00000。从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Waterloo”
texttt{“Waterloo”}
“Waterloo” 的行程有
2
texttt{2}
2 个，
(10
+
12)
/
2
=
11
texttt{(10 + 12) / 2 = 11}
(10 + 12) / 2 = 11
undergroundSystem.checkIn(10,
“Leyton”,
24);
texttt{undergroundSystem.checkIn(10, “Leyton”, 24);}
undergroundSystem.checkIn(10, “Leyton”, 24);
undergroundSystem.getAverageTime(“Leyton”,
“Waterloo”);
texttt{undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);}
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”); // 返回
11.00000
texttt{11.00000}
11.00000
undergroundSystem.checkOut(10,
“Waterloo”,
38);
texttt{undergroundSystem.checkOut(10, “Waterloo”, 38);}
undergroundSystem.checkOut(10, “Waterloo”, 38); // 乘客
10
texttt{10}
10 从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Waterloo”
texttt{“Waterloo”}
“Waterloo” 的时间是
38
–
24
=
14
texttt{38 – 24 = 14}
38 – 24 = 14
undergroundSystem.getAverageTime(“Leyton”,
“Waterloo”);
texttt{undergroundSystem.getAverageTime(“Leyton”, “Waterloo”);}
undergroundSystem.getAverageTime(“Leyton”, “Waterloo”); // 返回
12.00000
texttt{12.00000}
12.00000。从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Waterloo”
texttt{“Waterloo”}
“Waterloo” 的行程有
3
texttt{3}
3 个，
(10
+
12
+
14)
/
3
=
12
texttt{(10 + 12 + 14) / 3 = 12}
(10 + 12 + 14) / 3 = 12
示例 2：
输入：
[“UndergroundSystem”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”]
texttt{[“UndergroundSystem”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”,”checkIn”,”checkOut”,”getAverageTime”]}
[“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”]]
texttt{[[],[10,”Leyton”,3],[10,”Paradise”,8],[“Leyton”,”Paradise”],[5,”Leyton”,10],[5,”Paradise”,16],[“Leyton”,”Paradise”],[2,”Leyton”,21],[2,”Paradise”,30],[“Leyton”,”Paradise”]]}
[[],[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]
texttt{[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]}
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
解释：
UndergroundSystem
undergroundSystem
=
new
UndergroundSystem();
texttt{UndergroundSystem undergroundSystem = new UndergroundSystem();}
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10,
“Leyton”,
3);
texttt{undergroundSystem.checkIn(10, “Leyton”, 3);}
undergroundSystem.checkIn(10, “Leyton”, 3);
undergroundSystem.checkOut(10,
“Paradise”,
8);
texttt{undergroundSystem.checkOut(10, “Paradise”, 8);}
undergroundSystem.checkOut(10, “Paradise”, 8); // 乘客
10
texttt{10}
10 从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Paradise”
texttt{“Paradise”}
“Paradise” 的时间是
8
–
3
=
5
texttt{8 – 3 = 5}
8 – 3 = 5
undergroundSystem.getAverageTime(“Leyton”,
“Paradise”);
texttt{undergroundSystem.getAverageTime(“Leyton”, “Paradise”);}
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // 返回
5.00000
texttt{5.00000}
5.00000。
(5)
/
1
=
5
texttt{(5) / 1 = 5}
(5) / 1 = 5
undergroundSystem.checkIn(5,
“Leyton”,
10);
texttt{undergroundSystem.checkIn(5, “Leyton”, 10);}
undergroundSystem.checkIn(5, “Leyton”, 10);
undergroundSystem.checkOut(5,
“Paradise”,
16);
texttt{undergroundSystem.checkOut(5, “Paradise”, 16);}
undergroundSystem.checkOut(5, “Paradise”, 16); // 乘客
5
texttt{5}
5 从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Paradise”
texttt{“Paradise”}
“Paradise” 的时间是
16
–
10
=
6
texttt{16 – 10 = 6}
16 – 10 = 6
undergroundSystem.getAverageTime(“Leyton”,
“Paradise”);
texttt{undergroundSystem.getAverageTime(“Leyton”, “Paradise”);}
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // 返回
5.50000
texttt{5.50000}
5.50000。
(5
+
6)
/
2
=
5.5
texttt{(5 + 6) / 2 = 5.5}
(5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2,
“Leyton”,
21);
texttt{undergroundSystem.checkIn(2, “Leyton”, 21);}
undergroundSystem.checkIn(2, “Leyton”, 21);
undergroundSystem.checkOut(2,
“Paradise”,
30);
texttt{undergroundSystem.checkOut(2, “Paradise”, 30);}
undergroundSystem.checkOut(2, “Paradise”, 30); // 乘客
2
texttt{2}
2 从
“Leyton”
texttt{“Leyton”}
“Leyton” 到
“Paradise”
texttt{“Paradise”}
“Paradise” 的时间是
30
–
21
=
9
texttt{30 – 21 = 9}
30 – 21 = 9
undergroundSystem.getAverageTime(“Leyton”,
“Paradise”);
texttt{undergroundSystem.getAverageTime(“Leyton”, “Paradise”);}
undergroundSystem.getAverageTime(“Leyton”, “Paradise”); // 返回
6.66667
texttt{6.66667}
6.66667。
(5
+
6
+
9)
/
3
=
6.66667
texttt{(5 + 6 + 9) / 3 = 6.66667}
(5 + 6 + 9) / 3 = 6.66667
数据范围
-
1
≤
id,
t
≤
10
6
texttt{1} le texttt{id, t} le texttt{10}^texttt{6}
1≤id, t≤106 -
1
≤
stationName.length,
startStation.length,
endStation.length
≤
10
texttt{1} le texttt{stationName.length, startStation.length, endStation.length} le texttt{10}
1≤stationName.length, startStation.length, endStation.length≤10 - 所有的字符串包含大写字母、小写字母和数字
- 总共最多调用
2
×
10
4
texttt{2} times texttt{10}^texttt{4}
2×104 次checkIn
texttt{checkIn}
checkIn、checkOut
texttt{checkOut}
checkOut 和getAverageTime
texttt{getAverageTime}
getAverageTime - 与标准答案误差在
10
-5
texttt{10}^texttt{-5}
10-5 以内的结果都视为正确结果
解法
思路和算法
这道题要求收集乘客在不同站之间的花费时间，并根据这些数据计算从一个地铁站到另一个地铁站的平均花费时间。
一个乘客在
t
1
t_1
t1 时刻进入地铁站
s
1
s_1
s1，然后在
t
2
t_2
t2 时刻离开地铁站
s
2
s_2
s2，则该乘客从地铁站
s
1
s_1
s1 到地铁站
s
2
s_2
s2 的花费时间是
t
2
−
t
1
t_2 – t_1
t2−t1。为了记录乘客在不同站之间的花费时间，需要使用哈希表记录每个乘客的卡号以及该乘客进入的地铁站和进站时刻，当乘客离开另一个地铁站时，可以根据乘客的卡号得到该乘客进入的地铁站和进站时刻，结合乘客离开的地铁站和出站时刻即可得到由起点和终点组成的旅程信息，以及花费时间。
为了计算两个特定地铁站之间的平均花费时间，需要使用哈希表记录每个旅程以及该旅程的总时间与次数。当乘客离开地铁站时，即可得到该乘客的旅程信息和花费时间，将该旅程的总时间加上该乘客的花费时间，将该旅程的次数加
1
1
1，总时间除以次数即为该旅程的平均花费时间。
基于上述分析，需要维护两个哈希表，分别记录进站信息和旅程时间。
构造方法中，将两个哈希表初始化。
对于
checkIn
textit{checkIn}
checkIn 操作，根据站名和时刻构造进站信息，将卡号和进站信息存入进站信息哈希表。
对于
checkOut
textit{checkOut}
checkOut 操作，根据卡号
id
textit{id}
id 从进站信息哈希表中得到进站信息，从进站信息得到进入的地铁站
startStation
textit{startStation}
startStation 和进站时刻
startTime
textit{startTime}
startTime，结合离开的地铁站
stationName
textit{stationName}
stationName 和出站时刻
t
t
t，得到旅程为进入的地铁站和离开的地铁站拼接之后的字符串，花费时间为
t
−
startTime
t – textit{startTime}
t−startTime，将旅程和花费时间存入旅程时间哈希表。
对于
getAverageTime
textit{getAverageTime}
getAverageTime 操作，根据进入的地铁站
startStation
textit{startStation}
startStation 和离开的地铁站
endStation
textit{endStation}
endStation 得到旅程，从旅程时间哈希表中得到该旅程的总时间与次数，总时间除以次数即为该旅程的平均花费时间。
由于所有的事件都按时间顺序出现，同一个乘客一定是先进站后出站，当一个乘客出站之后，不可能在进站之前第二次出站，因此当乘客出站时，不需要将该乘客的进站信息从进站信息哈希表中删除。
代码
class UndergroundSystem {
private class CheckInInfo {
private String station;
private int time;
public CheckInInfo(String station, int time) {
this.station = station;
this.time = time;
}
public String getStation() {
return station;
}
public int getTime() {
return time;
}
}
private MapInteger, CheckInInfo> checkInMap;
private MapString, int[]> tripTimeMap;
public UndergroundSystem() {
checkInMap = new HashMapInteger, CheckInInfo>();
tripTimeMap = new HashMapString, int[]>();
}
public void checkIn(int id, String stationName, int t) {
CheckInInfo info = new CheckInInfo(stationName, t);
checkInMap.put(id, info);
}
public void checkOut(int id, String stationName, int t) {
CheckInInfo info = checkInMap.get(id);
String startStation = info.getStation();
int startTime = info.getTime();
String key = startStation + "," + stationName;
tripTimeMap.putIfAbsent(key, new int[2]);
int[] time = tripTimeMap.get(key);
time[0] += t - startTime;
time[1]++;
}
public double getAverageTime(String startStation, String endStation) {
String key = startStation + "," + endStation;
int[] time = tripTimeMap.get(key);
return 1.0 * time[0] / time[1];
}
}
复杂度分析
-
时间复杂度：构造方法和各项操作的时间复杂度都是
O
(
1
)
O(1)
O(1)。构造方法初始化两个哈希表，各项操作均为操作哈希表和计算花费时间，因此时间复杂度是
O
(
1
)
O(1)
O(1)。这里将字符串操作的时间视为
O
(
1
)
O(1)
O(1)。
-
空间复杂度：
O
(
n
)
O(n)
O(n)，其中
n
n
n 是所有方法的总调用次数。需要使用两个哈希表分别记录进站信息和旅程时间，每个哈希表中的元素个数都是
O
(
n
)
O(n)
O(n)。
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
