题目链接如下：

https://leetcode.cn/problems/design-underground-system/description/?envType=study-plan-v2&envId=programming-skills

我的方法

本题目我设计的解决方案如下：

class UndergroundSystem {
public:

    typedef struct TimeScope{//用哈希表记录指定的两个地铁站之间已经产生的路程时间长度
        vector<int>scopes;
        string beginStation;
        string endStation;
    }timeScope;
    vector<timeScope>ts;

    typedef struct CheckinMark{//用顺序表记录用户的一次乘坐经历
        int beginTime;
        int endTime;
        string beginStation;
        string endStation;
    }checkinMark;
    checkinMark cm[1000001];
    
    UndergroundSystem() {
        for(int i=0;i<=1000000;i++){
            cm[i].beginTime=-1;
            cm[i].endTime=-1;
        }
    }
    
    void checkIn(int id, string stationName, int t) {
        cm[id].beginStation=stationName;
        cm[id].beginTime=t;
    }
    
    void checkOut(int id, string stationName, int t) {
        cm[id].endStation=stationName;
        cm[id].endTime=t;
        for(int i=0;i<ts.size();i++){
            if(ts[i].beginStation==cm[id].beginStation&&ts[i].endStation==cm[id].endStation){
                ts[i].scopes.push_back(cm[id].endTime-cm[id].beginTime);
            }
        }
        timeScope newTs;
        newTs.scopes.push_back(cm[id].endTime-cm[id].beginTime);
        newTs.beginStation=cm[id].beginStation;
        newTs.endStation=cm[id].endStation;
        ts.push_back(newTs);
    }
    
    double getAverageTime(string startStation, string endStation) {
        double sum=0;
        for(int i=0;i<ts.size();i++){
            if(ts[i].beginStation==startStation&&ts[i].endStation==endStation){
                for(int j=0;j<ts[i].scopes.size();j++){
                    sum+=ts[i].scopes[j];
                }
                return sum/ts[i].scopes.size();
            }
        }
        return 0;
    }
};

主要使用了timeScope和checkinMark两个自定义数据结构，并进行维护。

我想到了使用用户id作为一个key，来设计哈希表。

但由于我在哈希表使用方面的想象力不足，对于单个用户的访问记录，没能想到使用<起始站，终点站>键值对作为哈希表的key。而我的方案使用了顺序表，在时间复杂度上要远远高于使用哈希表的方案。

题解答案

class UndergroundSystem {
public:
    using Start = pair <string, int>;
    using StartEnd = pair <string, string>;
    using SumAndAmount = pair <int, int>;

    struct StartEndHash {
        int operator() (const StartEnd& x) const{
            return hash <string> () (x.first + x.second);
        }
    };

    unordered_map <int, Start> startInfo;
    unordered_map <StartEnd, SumAndAmount, StartEndHash> table;
    
    UndergroundSystem() {}
    
    void checkIn(int id, string stationName, int t) {
        startInfo[id] = {stationName, t};
    }
    
    void checkOut(int id, string stationName, int t) {
        auto startTime = startInfo[id].second;
        table[{startInfo[id].first, stationName}].first += t - startTime;
        table[{startInfo[id].first, stationName}].second++;
    }
    
    double getAverageTime(string startStation, string endStation) {
        auto sum = table[{startStation, endStation}].first;
        auto amount = table[{startStation, endStation}].second;
        return double(sum) / amount;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/design-underground-system/solutions/178324/she-ji-di-tie-xi-tong-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解设计的两个数据结构均为哈希表。

• 第一个哈希表为startInfo

  key: 用户id

  value: {起始站，起始时间}

• 第二个哈希表为table

  key:<起始站，终点站>

  value:<总时长，总人数>

注意在第二个表的设计中，unordered_map指定了三个参数：

struct StartEndHash {
        int operator() (const StartEnd& x) const{
            return hash <string> () (x.first + x.second);
        }
    };

unordered_map <StartEnd, SumAndAmount, StartEndHash> table;

这是因为其Key StartEnd是自定义的pair类型，需要指定其产生单一值的key的方法。

本题目涉及到的哈希表设计方法，值得记录。