1797. 设计一个验证系统

题目链接：1797. 设计一个验证系统

方法：哈希

解题思路

注意：在判断 \(tokenId\) 是否出现过时，使用 \(Time.count(tokenId)\)，而不是使用 \(Time[tokenId]\)，因为只要使用之后，\(tokenId\) 就会被添加进 \(map\) 中，影响后续计数的结果。

代码

class AuthenticationManager {
private:
    int TimeToLive;
    unordered_map<string, int> Time;
public:
    AuthenticationManager(int timeToLive) {
        TimeToLive = timeToLive;
    }
    
    void generate(string tokenId, int currentTime) {
        Time[tokenId] = currentTime;
    }
    
    void renew(string tokenId, int currentTime) {
        if (!Time.count(tokenId) || Time[tokenId] + TimeToLive <= currentTime) return ;
        Time[tokenId] = currentTime;
    }
    
    int countUnexpiredTokens(int currentTime) {
        int cnt = 0;
        for (auto &t : Time) {
            if (t.second + TimeToLive > currentTime) cnt ++ ;
        }
        return cnt;
    }
};
/**
 * Your AuthenticationManager object will be instantiated and called as such:
 * AuthenticationManager* obj = new AuthenticationManager(timeToLive);
 * obj->generate(tokenId,currentTime);
 * obj->renew(tokenId,currentTime);
 * int param_3 = obj->countUnexpiredTokens(currentTime);
 */

复杂度分析

时间复杂度：构造函数—\(O(1)\)，\(generate()\)—\(O(1)\)，\(renew()\)—\(O(1)\)，\(countUnexpiredTokens()\)—\(O(n)\)，\(n\) 为 \(generate()\) 加入的验证码数量。
空间复杂度：\(O(n)\)，\(map\) 中元素的个数。