题解 | #牛群的优先级缓存# 哈希表和队列

用一个哈希表和一个队列记录当前信息，根据需求进行操作

class Solution {
  private:
    int capacity; // 容量
    unordered_map<int, int> mp;// 记录映射 cowId-priority
    queue<int> qu;// 记录当前的牛使用信息
    // 初始化缓存
    void CowCache(int capacity) {
        this->capacity = capacity;
    }
    // 返回优先级
    int getPriority(int cowId) {
        if (mp.count(cowId)) {
            // 队列已满，需要弹出最久未使用
            if (qu.size() >= capacity) {
                qu.pop();
            }
            // 新的被使用的 cowId 入队
            qu.push(cowId);
            return mp[cowId];
        } else {
            return -1;
        }
    }
    // 插入或更新优先级
    void setPriority(int cowId, int priority) {
        // 队列已满，分别在 队列 和 mp 中删去队头元素
        if (qu.size() >= capacity) {
            int del = qu.front();
            qu.pop();
            mp.erase(del);
        }
        // 更新记录
        qu.push(cowId);
        mp[cowId] = priority;
    }
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param operations string字符串vector
     * @param args int整型vector<vector<>>
     * @return int整型vector
     */
    vector<int> cowCacheOperations(vector<string>& operations,
                                   vector<vector<int> >& args) {
        vector<int> ans;
        for (int i = 0; i < operations.size(); i++) {
            if (operations[i] == "CowCache") {
                CowCache(args[i][0]);
                ans.push_back(-2);
            } else if (operations[i] == "getPriority") {
                ans.push_back(getPriority(args[i][0]));
            } else if (operations[i] == "setPriority") {
                setPriority(args[i][0], args[i][1]);
                ans.push_back(-2);
            }
        }
        return ans;
    }
};

时间复杂度：

1、初始化缓存，O(1)

2、查询优先级，查找牛ID是否存在于 unordered_map 中：O(1) 平均时间复杂度

如果队列已满，弹出队首元素：O(1)

将牛ID插入队列：O(1)

总时间复杂度为 O(1)

3、更新优先级，如果队列已满，删除队首元素并在 unordered_map 中删除相应记录：O(1)

将牛ID插入队列并更新映射：O(1)

总时间复杂度为 O(1)

4、执行所有操作，遍历 operations 列表，对每个操作调用相应方法。假设有 n 个操作，则时间复杂度为 O(n)

综上，每个操作的时间复杂度为 O(1)，所有操作的总时间复杂度为 O(n)

空间复杂度：

1、mp：存储最多 capacity 个牛ID和优先级，每个牛ID和优先级占用 O(1) 空间，最多 O(capacity)

2、qu：存储最多 capacity 个牛ID，每个牛ID占用 O(1) 空间，最多 O(capacity)

3、operations 和 args：假设有 n 个操作，每个操作参数的大小固定或可忽略不计，则操作列表和参数列表的空间复杂度为 O(n)

4、ans：存储 n 个操作的结果，空间复杂度为 O(n)

综上，总空间复杂度为 O(capacity + n)