题目

错误解法

先分享一种错误解法。下面的这种错误解法错在很多个点上。首先，他每个操作不是O(1)的，时间复杂度就错了。第二，如果某个id先进出某两个站，然后再进了某个站，这个时候计算他的travel time是错的，因为按照下面这种解法会是出站时间小于进站时间，也就是这种解法不满足同一个id多次进出的情况。第三，如果某个idA进B出，然后C进D出，这个时候按下面的解法，在query(A,D)这个pair的时候就会被错误的包括进去，所以start和end必须是以pair的形式储存的

class UndergroundSystem:

    def __init__(self):
        self.checkin_dict = {}
        self.checkout_dict = {}
        

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        if stationName in self.checkin_dict:
            self.checkin_dict[stationName][id] = t
        else:
            self.checkin_dict[stationName] = {}
            self.checkin_dict[stationName][id] = t

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        if stationName in self.checkout_dict:
            self.checkout_dict[stationName][id] = t
        else:
            self.checkout_dict[stationName] = {}
            self.checkout_dict[stationName][id] = t

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        #print(self.checkin_dict)
        total_time = 0
        cnt = 0
        if startStation in self.checkin_dict and endStation in self.checkout_dict:
            for id,t in self.checkin_dict[startStation].items():
                if id in self.checkout_dict[endStation]:
                    cnt += 1
                    total_time += self.checkout_dict[endStation][id] - self.checkin_dict[startStation][id]
        return total_time/cnt

正确解法

这道题正确解法远没有这么复杂。前面这么些是因为默认了checkin和checkout的情况需要被储存下来，其实只要储存checkin，checkout的时候就可以直接计算相应的时间了

class UndergroundSystem:

    def __init__(self):
        self.checkin_dict = {}
        self.travel_time = collections.defaultdict(int)
        self.travel_cnt = collections.defaultdict(int)
        

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

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        startStation,start_t = self.checkin_dict[id]
        self.travel_time[(startStation,stationName)] += t - start_t
        self.travel_cnt[(startStation,stationName)] += 1
        

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        return self.travel_time[(startStation,endStation)]/self.travel_cnt[(startStation,endStation)]