05 August 2008
我们需要两张哈希表。一张用来存编号为 id 的乘客的进站信息，键为 id，值需要保存两个信息：站点名字和进站时间。另一张用来存放以 s 为起点站，e 为终点站的已经出站的乘客的信息，键为 (s, e)，值也需要保存两个信息：花费的总时间和已经出站的总人数。
在 checkIn 的时候，我们对第一张表进行操作，保存进站信息。在 checkOut 的时候，我们先从第一张表中查询这个 id 的进站信息 (startStation, startTime)，然后修改第二张表，把总时间加上 t - startTime，总人数自增一。在 getAverageTime 的时候直接查询第二张表得到 (sum, amount)，计算平均值。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class UndergroundSystem {
class Start {
String station;
int time;
public Start(String station, int time) {
this.station = station;
this.time = time;
}
}
class StartEnd {
String start;
String end;
public StartEnd(String start, String end) {
this.start = start;
this.end = end;
}
public int hashCode() {
return (start + end).hashCode();
}
public boolean equals(Object obj2) {
if (obj2 instanceof StartEnd) {
StartEnd startEnd2 = (StartEnd) obj2;
return this.start.equals(startEnd2.start) && this.end.equals(startEnd2.end);
}
return false;
}
}
class SumAmount {
int sum;
int amount;
public SumAmount(int sum, int amount) {
this.sum = sum;
this.amount = amount;
}
}
Map<Integer, Start> startInfo;
Map<StartEnd, SumAmount> table;
public UndergroundSystem() {
startInfo = new HashMap<Integer, Start>();
table = new HashMap<StartEnd, SumAmount>();
}
public void checkIn(int id, String stationName, int t) {
startInfo.put(id, new Start(stationName, t));
}
public void checkOut(int id, String stationName, int t) {
Start start = startInfo.get(id);
String startStation = start.station;
int startTime = start.time;
StartEnd startEnd = new StartEnd(startStation, stationName);
SumAmount sumAmount = table.getOrDefault(startEnd, new SumAmount(0, 0));
sumAmount.sum += t - startTime;
sumAmount.amount++;
table.put(startEnd, sumAmount);
}
public double getAverageTime(String startStation, String endStation) {
StartEnd index = new StartEnd(startStation, endStation);
SumAmount sumAmount = table.get(index);
int sum = sumAmount.sum, amount = sumAmount.amount;
return 1.0 * sum / amount;
}
}
/**
* 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);
*/
时间复杂度：从代码可以看出，这里 checkIn、checkOut 和 getAverageTime 的渐进时间复杂度都是 O(1)。
空间复杂度：这里我们用到了两张哈希表作为辅助空间。假设这里操作的总次数为 n，那么第一张表的键的总数为 O(n)，第二张表键的总数也为 O(n)，故渐进空间复杂度为 O(n ^ 2)。