Implement the class UndergroundSystem
that supports three methods:
1. checkIn(int id, string stationName, int t)
- A customer with id card equal to
id
, gets in the stationstationName
at timet
. - A customer can only be checked into one place at a time.
2. checkOut(int id, string stationName, int t)
- A customer with id card equal to
id
, gets out from the stationstationName
at timet
.
3. getAverageTime(string startStation, string endStation)
- Returns the average time to travel between the
startStation
and theendStation
. - The average time is computed from all the previous traveling from
startStation
toendStation
that happened directly. - Call to
getAverageTime
is always valid.
You can assume all calls to checkIn
and checkOut
methods are consistent. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.
Example 1:
Input ["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"]] Output [null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0] Explanation UndergroundSystem undergroundSystem = new UndergroundSystem(); undergroundSystem.checkIn(45, "Leyton", 3); undergroundSystem.checkIn(32, "Paradise", 8); undergroundSystem.checkIn(27, "Leyton", 10); undergroundSystem.checkOut(45, "Waterloo", 15); undergroundSystem.checkOut(27, "Waterloo", 20); undergroundSystem.checkOut(32, "Cambridge", 22); undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22) undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0 undergroundSystem.checkIn(10, "Leyton", 24); undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 11.0 undergroundSystem.checkOut(10, "Waterloo", 38); undergroundSystem.getAverageTime("Leyton", "Waterloo"); // return 12.0
Constraints:
- There will be at most
20000
operations. 1 <= id, t <= 10^6
- All strings consist of uppercase, lowercase English letters and digits.
1 <= stationName.length <= 10
- Answers within
10^-5
of the actual value will be accepted as correct.
Solution: Hashtable
For each user, store the checkin station and time.
For each trip (startStation + “_” + endStation), store the total time and counts.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class UndergroundSystem { public: UndergroundSystem() {} void checkIn(int id, string stationName, int t) { m_[id] = {stationName, t}; } void checkOut(int id, string stationName, int t) { const auto& [s0, t0] = m_[id]; string key = s0 + "_" + stationName; times_[key].first += (t - t0); ++times_[key].second; } double getAverageTime(string startStation, string endStation) { const auto& [sum, count] = times_[startStation + "_" + endStation]; return static_cast<double>(sum) / count; } private: unordered_map<int, pair<string, int>> m_; // id -> {station, t} unordered_map<string, pair<int, int>> times_; // trip -> {sum, count} }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment