2 min read leetcode

1396. Design Underground System

1396. Design Underground System
Photo by Markus Spiske / Unsplash

題意

  • 設計一個地鐵系統，含有幾個 function
    • void checkIn(int id, string stationName, int t)
      • id 從 stationName 的進站時間 t
    • void checkOut(int id, string stationName, int t)
      • id 從 stationName 的出站時間 t
    • double getAverageTime(string startStation, string endStation)
      • 計算兩個站之間平均進出站花費時間
      • 進出站方向相反，花費時間也可能不同
  • 假設每次 call getAverageTime 的時候，相關資料都已經完整可用

限制

  • 1 <= id, t <= $10^6$
  • 1 <= stationName.length, startStation.length, endStation.length <= 10
  • All strings consist of uppercase and lowercase English letters and digits.
  • There will be at most 2 * $10^4$ calls in total to checkIn, checkOut, and getAverageTime.
  • Answers within $10^{-5}$ of the actual value will be accepted.

題目思考

  • checkOut 被 call 的時間不固定，因此需要先為 id 建立好辨識方法，以便在 checkOut 時可取得對應資料並進行計算。
  • 每次有人 checkOut，都更新 startStation - endStation 的相關資料供之後查詢。

Solution

class UndergroundSystem {
private:
    unordered_map<int, pair<string, int>> customers;
    unordered_map<string, pair<long, int>> routes;
public:
    UndergroundSystem() {
        
    }
    
    void checkIn(int id, string stationName, int t) {
        customers[id] = { stationName, t };
    }
    
    void checkOut(int id, string stationName, int t) {
        int time = t - customers[id].second;
        string routingKey = customers[id].first + "-" + stationName;
        routes[routingKey].first += time;
        routes[routingKey].second += 1;

        customers.erase(id);
    }
    
    double getAverageTime(string startStation, string endStation) {
        string routingKey = startStation + "-" + endStation;
        return (double) routes[routingKey].first / routes[routingKey].second;
    }
};

/**
 * 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);
 */

時間與空間複雜度

  • 時間複雜度：
    由於使用 unordered_map 進行存取，每次執行 checkIn、checkOut 以及 getAverageTime 時，平均時間複雜度均為 O(1)。
  • 空間複雜度：
    • customers 用來儲存尚未完成出站的乘客資訊，最多可能同時容納所有尚未 checkOut 的乘客。
    • routes 用來儲存各路線 (startStation, endStation) 的累計時間和人次，若出現許多不同的站點組合，對應的鍵值也會相應增長。
      在最壞情況下，空間需求約為 O(N)，其中 N 為操作次數的總量。

Justin