My not so great Java accepted (> 21%)


  • 0
    P
    private int capacity;
    private Map<Integer, Integer> keyValue;
    private Map<Integer, Integer> keyFreq;
    private Map<Integer, List<Integer>> freqKey;
    
    LFUCache(int capacity) {
        this.capacity = capacity;
        this.keyValue = new HashMap<>();
        this.keyFreq = new HashMap<>();
        this.freqKey = new HashMap<>();
    }
    
    private void addKeyToFreqKey(int key) {
        int freq = keyFreq.get(key);
        
        // Create list if it doesn't exist
        if (!freqKey.containsKey(freq)) {
            freqKey.put(freq, new ArrayList<>());
        }
        
        if (freqKey.get(freq).contains(key)) {
            // Reset at beginning of list by removing and re-adding
            freqKey.get(freq).remove((Integer) key);
        }
        freqKey.get(freq).add(key);
    }
    
    private void removeKeyFromFreqKey(int key) {
        int freq = keyFreq.get(key);
        freqKey.get(freq).remove((Integer) key);
        if (freqKey.get(freq).isEmpty()) {
            freqKey.remove(freq);
        }
    }
    
    private void removeLeastUsed() {
        int minKey = -1;
        int minFreq = -1;
        for (Integer currentFreq : freqKey.keySet()) {
            if (minFreq == -1 || currentFreq < minFreq) {
                minKey = freqKey.get(currentFreq).get(0);
                minFreq = currentFreq;
            }
        }
        
        keyValue.remove(minKey);
        removeKeyFromFreqKey(minKey);
        keyFreq.remove(minKey);
        
    }
    
    public void set(int key, int value) {
        if (capacity <= 0) {
            return;
        }
        
        if (keyValue.containsKey(key)) {
            keyValue.put(key, value);
            get(key); // Increase freq
            return;
        }
        
        if (keyValue.size() + 1 > capacity) {
            removeLeastUsed();
        }
        
        keyValue.put(key, value);
        keyFreq.put(key, 0);
        addKeyToFreqKey(key);
    }
    
    public int get(int key) {
        if (!keyValue.containsKey(key)) {
            return -1;
        }
        
        int oldFreq = keyFreq.get(key);
        int newFreq = oldFreq + 1;
        
        // Removing from old frequency
        removeKeyFromFreqKey(key);
        
        // Update key-frequency map with new frequency
        keyFreq.put(key, newFreq);
        
        // Adding to new frequency
        addKeyToFreqKey(key);
        
        return keyValue.get(key);
    }

Log in to reply
 

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