My solution using ArrayList (without creating a new object class) TLE....


  • 0
    C

    By updating the two ArrayList together, we can keep track of the information we need :

    public class LRUCache {
    
        private List<Integer> keys;
        private List<Integer> values;
        private int capacity;
        
        public LRUCache(int capacity) {
            this.keys = new ArrayList<Integer>();
            this.values = new ArrayList<Integer>();
            this.capacity = capacity;
        }
        
        public int get(int key) {
            int index = keys.indexOf(key);
            if (index == -1) {
                return -1;
            } else {
                keys.remove(index);
                int v = values.remove(index);
                keys.add(key);
                values.add(v);
                return v;
            }
        }
        
        public void set(int key, int value) {
            int index = keys.indexOf(key);
            if (index >= 0) {  // the key is already in the cache
                values.remove(index);
                values.add(value);
                keys.remove(index);
                keys.add(key);
            } else {
                // the key is not in the Cache yet
                if (keys.size() < capacity) { //  the cache is not full
                    keys.add(key);
                    values.add(value);
                } else {  // the cache is full
                    keys.remove(0);
                    values.remove(0);
                    keys.add(key);
                    values.add(value);
                }
            }
        }
    }

  • 0
    S

    Pay attention to "Writing code? Select all code block then click on the {} button to preserve code formatting.” above text editor.


  • 0
    C

    Thx~ I've updated it


  • 0
    S

    Appreciate updating.


  • 0
    W

    I copied to OJ and it is giving me TLE...


  • 0
    C

    yeh, I tried again and it gave me the TLE as well.... I guess they added some new testing? It worked before...


  • 0
    W

    thanks... isn't looking for an element in arraylist O(n) time? Thus the get function is O(n)?


  • 0
    C

    you are right! I think this solution will not work then... Gonna use another data structure. Thx~


  • 0
    H

    Class Class is a template for creating objects which defines its state and behavior. A class contains field and method to define the state and behavior of its object.... for more click here


Log in to reply
 

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