设为首页 加入收藏

TOP

LRU Cache有个问题解答
2014-09-18 13:06:50 来源: 作者: 【 】 浏览:97
Tags:LRU  Cache 问题解答

    [LeetCode]LRU Cache有个问题,求大神解答

    题目:

    Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

    get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

    set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

    这是我的代码:

    1 class LRUCache{

    2 public:

    3     int num;

    4     int max;

    5     list<int> latest_key;         //用于保存使用情况,队头是最久未使用的,队尾是最近使用的

    6     unordered_map<int, int> cache;   //用于保存key,value

    7

    8     LRUCache(int capacity) {

    9         num = 0;

    10         max = capacity;

    11     }

    12

    13     int get(int key) {

    14         unordered_map<int, int>::iterator it = cache.find(key);

    15         list<int>::iterator iter;

    16         if (it == cache.end())  //如果没有找到key

    17             return -1;

    18         else            //如果找到了key,就在对应的最近latest队列里面修改key的位置,先把key所在的位置删除,再把key放到队尾

    19         {

    20             iter = latest_key.begin();

    21             while (*iter != key)

    22                 iter++;

    23             latest_key.erase(iter);

    24             latest_key.push_back(key);

    25             return it->second;

    26         }

    27     }

    28

    29     void set(int key, int value) {

    30         unordered_map<int, int>::iterator it = cache.find(key);

    31         list<int>::iterator iter;

    32         if (it != cache.end())  //如果要插入的已经有key存在,就先在优先队列里面找到key出现的位置,删除,再把key插入队尾

    33         {

    34             it->second = value;

    35             iter = latest_key.begin();

    36             while (*iter != key)

    37                 iter++;

    38             latest_key.erase(iter);

    39             latest_key.push_back(key);

    40         }

    41         else            //如果要插入的不存在

    42         {

    43             if (num<max)  //如果不超过cache容量,则直接在cahe中插入,再在队尾添加该key

    44             {

    45                 num++;

    46                 cache.insert(std::pair< int, int >(key, value));

    47                 latest_key.push_back(key);

    48             }

    49             else      //如果cache已经满了,则根据队头元素,在cache删除对应键值,再在队列中删除这个队头,之后,把新要插入的键值插入cache中,把新key插入队尾

    50             {

    51                 int latest = latest_key.front();

    52                 cache.erase(latest);

    53                 latest_key.pop_front();

    54                 cache.insert(std::pair< int, int >(key, value));

    55                 latest_key.push_back(key);

    56             }

    57         }

    58     }

    59 };

    当我把代码中出现:

    1  iter = latest_key.begin();

    2  while (*iter != key)

    3     iter++;

    部分替换为:

    1 iter=find(latest_key.begin(),latest_key.end(),key);

    就会报错:

    Time Limit Exceeded

    Last executed input: 2048,[set(1178,3401),set(903,6060)……

    我大致查了一下find的实现机制,也是遍历啊,按理说这两者效率差不多,为什么替换之后就不能通过?而替换之前能通过,求大神解答!!

 

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇哈夫曼编码与解码 下一篇ADO访问Access数据库错误解决

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·About - Redis (2025-12-26 08:20:56)
·Redis: A Comprehens (2025-12-26 08:20:53)
·Redis - The Real-ti (2025-12-26 08:20:50)
·Bash 脚本教程——Li (2025-12-26 07:53:35)
·实战篇!Linux shell (2025-12-26 07:53:32)