Why does this way timeout???


  • 0
     class LRUCache{
      struct value_count
      {
        int value;
        int count;
      };
      typedef struct value_count Value_Count;
     public:
       LRUCache(int capacity) {
                LRU_Capacity = capacity;
                current_LRU_Numbers = 0;
        }
    
    int get(int key) {
        map<int,Value_Count>::iterator iter_Get = cache.find(key);
        if(iter_Get!=cache.end())
        {
            inc();
            iter_Get->second.count = 0;
            return iter_Get->second.value;
        }
        return -1;
    }
    
    void set(int key, int value) {
        map<int,Value_Count>::iterator iter_Set = cache.find(key);
        if(iter_Set!=cache.end())
            return;
        if(current_LRU_Numbers==LRU_Capacity)
        {//去掉一个LRU cache
            map<int,Value_Count>::iterator iter1 = cache.begin();
            map<int,Value_Count>::iterator iter2 = iter1;
            iter2++;
            for(;iter2!=cache.end();iter2++)
            {
                if((iter2->second.count)>(iter1->second.count))
                    iter1 = iter2;
            }
            cache.erase(iter1);
            current_LRU_Numbers--;
        }
        Value_Count p;
        p.value = value;
        p.count = 0;
        inc();
        cache.insert(make_pair(key,p));
        current_LRU_Numbers++;
    }
    
    void inc()
    {
        map<int,Value_Count>::iterator iter_temp;
        for(iter_temp = cache.begin();iter_temp != cache.end();iter_temp++)
        {
            iter_temp->second.count++;
        }
    }
         private:
              int LRU_Capacity;
              int current_LRU_Numbers;
              map<int,Value_Count> cache;
          };

  • 1
    N

    Because the time complexity is O(n), The overall run time complexity should be O(1), try hash.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.