题解 | #设计LFU缓存结构#

import java.util.LinkedHashMap;
import java.util.Map;

public class Solution {
    static class Cache {
        Map<Integer, Integer> data = null;
        Map<Integer, Integer> count = null;
        int capacity = 0;

        public Cache(int k) {
            data = new LinkedHashMap(k);
            count = new LinkedHashMap(k);
            capacity = k;
        }

        public void set(int key, int value) {
            if (data.containsKey(key)) {
                data.put(key, value);
                count.put(key, count.getOrDefault(key, 0) + 1);
            } else if (data.size() >= capacity) {
                int k = getMinKey();
                data.remove(k);
                count.remove(k);
                data.put(key, value);
                count.put(key, count.getOrDefault(key, 0) + 1);
            } else {
                data.put(key, value);
                count.put(key, count.getOrDefault(key, 0) + 1);
            }
        }

        public int get(int key) {
            if (data.containsKey(key)) {
                int value = data.get(key);
                count.put(key, count.getOrDefault(key, 0) + 1);
                return value;
            } else {
                return -1;
            }
        }

        public int getMinKey() {
            int key = -1;
            int min = Integer.MAX_VALUE;
            for (Map.Entry<Integer, Integer> e : count.entrySet()) {
                if (e.getValue() < min) {
                    min = e.getValue();
                    key = e.getKey();
                }
            }
            return key;
        }
    }

    public int[] LFU(int[][] operators, int k) {
        int len = 0;
        for (int i = 0; i < operators.length; i++) {
            if (operators[i][0] == 2) {
                len++;
            }
        }
        int[] res = new int[len];
        len = 0;
        Cache cache = new Cache(k);
        for (int i = 0; i < operators.length; i++) {
            switch (operators[i][0]) {
                case 1:
                    cache.set(operators[i][1], operators[i][2]);
                    break;
                case 2:
                    res[len++] = cache.get(operators[i][1]);
                    break;
            }
        }
        return res;
    }
}