Last case failed with only one wrong output number, I hava no idea about debugging with so many pairs of numbers...


  • 0
    S

    my output: ....... ,5818,1537,-1,4383, ........

    expected output: ....... ,5818,1537,102,4383, ........

    Only one of the output numbers is wrong.

    And I don't know how to fix it. Can any one help?

    It's my code:

    • I use two integer:

    • capacity is the max number of elements in the cache,

    • totalNum is the number of elements at this moment.

    • I use a map(cacheMap) to record (key:value)s .

      *And an integer array(keyArray) is needed to record the keys in cacheMap. The lastest used element is the first element, and the element to removed is at the last place(keyArray[capacity-1]).

      class LRUCache{
      public:
      LRUCache(int capacity) {
      this->capacity = capacity;
      this->totalNum = 0;
      keyArray = new int[capacity];
      }

      int get(int key) {
      map<int, int>::iterator it = cacheMap.find(key);
      if ( it != cacheMap.end() )
      {
      // tag the element is used currently
      moveTop(2, key);
      return it->second;
      }
      return -1;
      }

      void set(int key, int value) {
      if ( totalNum < capacity && this->cacheMap.find(key) == this->cacheMap.end() )
      totalNum++;
      this->moveTop(1, key);
      cacheMap[key] = value;
      }

      void moveTop(int op, int key)
      {
      int index = totalNum - 1;
      int keyToBeErased;

       for ( int i = 0; i < this->totalNum-1; i++ )
       {
           if ( this->keyArray[i] == key )
           {
               index = i;
           }
       }
       if(op == 1 && totalNum == capacity  && index == totalNum-1)
       {
           keyToBeErased = this->keyArray[capacity-1];
           cacheMap.erase(keyToBeErased);
       }
      
       for( int j = index-1; j >= 0; j-- )
       {
           this->keyArray[j+1] = this->keyArray[j];
       }
       this->keyArray[0] = key;
      

      }

      private:
      int capacity;
      map<int, int> cacheMap;
      int* keyArray; //the last one in this array is removed first.
      int totalNum;
      };


  • 0
    R

    Why don't you give some idea at the beginning? It sounds to me that you have used a hashmap and an array to build the LRU cache. Am I right?


  • 0
    S

    Yes, exactly like that. My question has been updated. Thank you!


  • 0
    R

    If you are using an array to store the chronological information. One issue is that you have to move all elements in the array if the last element is moved to the head. The time complexity would be N/2 on average.


  • 0
    S

    Yes, I knew it. Actually, I am not quite sure that if vector or list is a better choice. But I don't think it's the reason that I got only one wrong number in hundreds of output numbers...


Log in to reply
 

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