NEED HELP! Why my O(1) solution get TLE!!!!!????


  • -1
    X

    I am 100% sure my code works correctly.

    I have tried the testcase that I got TLE on my own machine (VC2013). It literally takes only 3ms!
    I am not sure about the performance under g++.

    Somebody please HELP me about this. Thanks so much!

    I doubt the time limit is too tight.

    class LRUCache{
      unordered_map<int, list<pair<int, int>>::iterator> M;
      list<pair<int, int> > L;  // list of  (key,value) pair
      int cap;
    public:
      LRUCache(int capacity) {
        L.clear();
        M.clear();
        cap = capacity;
      }
    
      int get(int key) {
        if (M.count(key) == 0) return -1;
        else {
          auto it = M[key];
          int value = it->second;
          L.erase(it);
          L.push_front(make_pair(key, value));
          M[key] = L.begin();
          return value;
        }
      }
    
      void set(int key, int value) {
        if (M.count(key) != 0){
          auto it = M[key];
          L.erase(it);
        }
        L.push_front(make_pair(key, value));
        M[key] = L.begin();
        if (L.size() >= cap) {
          int removed_key = prev(L.end())->first;
          L.pop_back();
          M.erase(removed_key);
        }
      }
    };

  • 0
    A

    I suggest you use a set to record existing keys to avoid useless iterating when key is invalid.

    Notice: you should know set is implemented as tree, so it's time complexity is NlgN

    I found one's solution without lib tools is easy to TLE.


Log in to reply
 

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