Leetcode 460.LFU缓存【C++】

地址：https://leetcode-cn.com/problems/lfu-cache/

题目

请你为最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

• get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
• put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。

「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

进阶：

你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

解题思路

首先，题目涉及到的几个数据：

• capacity ：容量
• key 、 value 、 frequency ：分别是码、值、频次，并且这三项数据是一一对应的关系，所以我定义了一个 vector<pair<pair<int, int>, int>> 类型的数组来存储。vec.first 即键值对 {key, value} ，vec.second 即该键值对对应的频次。

起初我的想法是，需要什么就去数组里遍历查找，但是后面发现，频次可以找到最低的频次，但是同样频次的两个数据怎么判断哪一个离得近哪一个离得远呢？所以我另外定义了一个函数 rearrange(int index) ，每次 get 或 put 之后就对该项数据重排序，以保证数组始终是以频次最高且最近使用的排在前面，而频次低且离得远的排在后面。对于容量已满但要插入新数据的情况，就可以直接 vec.pop_back() 删除数组末尾的元素，并在末尾插入新元素。

需要注意，如果容量为0的话，put() 不应该执行任何操作，get() 默认将返回 -1 。

代码

class LFUCache {
private:
    int capacity;
    vector<pair<pair<int, int>, int>> vec;//默认使用频率高切最近使用的排在前面
public:
    LFUCache(int capacity) {
        this->capacity = capacity;
    }

    //每当get()或者put()的时候都重新对这个元素的位置进行排序
    void rearrange(int index) {
        //即使频率相同，但由于当前元素为最近使用，所以也应该排在前面
        for (int j = index - 1; j >= 0; j--) {
            if (vec[j + 1].second >= vec[j].second) {
                pair<pair<int, int>, int> tmp = vec[j + 1];
                vec[j + 1] = vec[j];
                vec[j] = tmp;
            }
        }
    }

    int get(int key) {
        for (int i = 0; i < vec.size(); i++) {
            if (vec[i].first.first == key) {
                vec[i].second++;
                int val = vec[i].first.second;
                rearrange(i);//频率改变，对其重排序
                return val;
            }
        }
        return -1;//容量为0或者不存在这个元素默认返回-1
    }

    void put(int key, int value) {
        //容量为0无法新增
        if (capacity == 0)
            return;
        for (int i = 0; i < vec.size(); i++) {
            //已存在值为key的元素应该更新其value，并将其频率+1
            if (vec[i].first.first == key) {
                vec[i].first.second = value;
                vec[i].second++;
                rearrange(i);//频率改变，对其重排序
                return;
            }
        }
        //元素不存在且容量未满
        if (vec.size() < capacity) {
            vec.push_back({ {key,value},0 });
            rearrange(vec.size() - 1);
            return;
        }
        //元素不存在但容量已满
        else {
            vec.pop_back();//末尾元素就是最最远且少使用的元素
            vec.push_back({ {key,value},0 });
            rearrange(vec.size() - 1);
        }
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */