Leetcode 460.LFU缓存【C++】

本文最后更新于:2020年7月4日 晚上

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

题目

请你为最不经常使用(LFU)缓存算法设计并实现数据结构。它应该支持以下操作:getput

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

「项的使用次数」就是自插入该项以来对其调用 getput 函数的次数之和。使用次数会在对应项被移除后置为 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 :容量
  • keyvaluefrequency :分别是码、值、频次,并且这三项数据是一一对应的关系,所以我定义了一个 vector<pair<pair<int, int>, int>> 类型的数组来存储。vec.first 即键值对 {key, value}vec.second 即该键值对对应的频次。

起初我的想法是,需要什么就去数组里遍历查找,但是后面发现,频次可以找到最低的频次,但是同样频次的两个数据怎么判断哪一个离得近哪一个离得远呢?所以我另外定义了一个函数 rearrange(int index) ,每次 getput 之后就对该项数据重排序,以保证数组始终是以频次最高且最近使用的排在前面,而频次低且离得远的排在后面。对于容量已满但要插入新数据的情况,就可以直接 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);
 */