---
# System prepended metadata

title: 1396. Design Underground System
tags: [Leetcode, Bloomberg, Medium]

---

# 1396. Design Underground System
###### tags: `Leetcode` `Medium` `Bloomberg`
Link: https://leetcode.com/problems/design-underground-system/
## 思路
用两个HashMap存
id->进入的station，进去的时间
进入的station，出去的station->时间，人数

第一个HashMap没有设计成id，station->时间的原因是，同一个是一次只能进一个站，另外在发现这个人出站的时候，可以用```inTime.remove(id);```把这个id删掉节省空间

这样呼叫每个函数的时间复杂度是O(1)，空间复杂度是O(P+S^2)，P是客流量最大的时候的人数，S是station的数量
## Code
```java=
class UndergroundSystem {
    Map<Integer,Pair<String, Integer>> inTime;
    Map<Pair<String, String>, Pair<Double, Double>> averageTime;
    public UndergroundSystem() {
        inTime = new HashMap<>();
        averageTime = new HashMap<>();
    }
    
    public void checkIn(int id, String stationName, int t) {
        inTime.put(id, new Pair<String, Integer>(stationName, t));
    }
    
    public void checkOut(int id, String stationName, int t) {
        int timeIn = inTime.get(id).getValue();
        String stationIn = inTime.get(id).getKey();
        int time = t-timeIn;
        Pair<String, String> stationPair = new Pair<>(stationIn, stationName);
        if(!averageTime.containsKey(stationPair)){
            averageTime.put(stationPair, new Pair<Double, Double>((double)t-timeIn,1.0));
        }
        else{
            Pair<Double, Double> oldTimePair = averageTime.get(stationPair);
            double totalTime = oldTimePair.getKey();
            double totalPpl = oldTimePair.getValue();
            averageTime.put(stationPair, new Pair<Double, Double>(totalTime+time, totalPpl+1));
        }
        inTime.remove(id);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        Pair<String, String> stationPair = new Pair<>(startStation, endStation);
        Pair<Double, Double> timePair = averageTime.get(stationPair);
        return timePair.getKey()/timePair.getValue();
    }
}
```