Leetcode 1396 - Design Underground System

題目

Problem#

問你能不能實作一個地鐵乘客系統，紀錄乘客上、下車時間，並可以用來統計站與站之間的平均搭乘時間。

• void checkIn(int id, string stationName, int t)
  • 乘客 id 在時間 t 在 stationName 上車
• void checkOut(int id, string stationName, int t)
  • 乘客 id 在時間 t 在 stationName 下車
• double getAverageTime(string startStation, string endStation)
  • 回傳從 startStation 到 endStation 的平均搭乘時間

1. 從 start 到 end 與 end 到 start 的時間可能不同
2. 在 getAverageTime() 呼叫前一定至少會有一組 start 與 end
3. 成對的 checkIn 與 checkOut 才會被算進平均時間中

測資限制#

• $1 \le id, t \le 10^6$
• $1 \le name \le 10$
• 最多會呼叫 $2 \times 10^4$ 次
• 答案精確度 $10^{-5}$

想法#

維護一個資料結構，用於紀錄乘客(id)進站的站點與時間，接著出站的時候，用乘客的id去找到進站的時間，便可計算時間差，而會貢獻在平均時間中。記得也要記錄從站點 a 到站點 b 總共幾個人搭過。

• 時間複雜度: $\mathcal{O}(n\log{n})$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

賞析#

也可以用 unordered_map 來記錄站點與總搭乘時間, 搭乘人數的關係