题解 | 设计LFU缓存结构

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    int time = 0;

    PriorityQueue<Node> pq = new PriorityQueue<Node>(new Comparator<Node>() {
        public int compare(Node n1, Node n2) {
            if (n1.count == n2.count) return n1.time - n2.time;
            return n1.count - n2.count;
        }
    });

    Map<Integer, Node> cache = new HashMap<>();

    class Node {
        int key;
        int val;
        int count;
        int time;

        Node(int key, int val, int time) {
            this.key = key;
            this.val = val;
            this.count = 1;
            this.time = time;
        }
    }

    public int[] LFU (int[][] operators, int k) {
        // write code here
        List<Integer> list = new ArrayList<>();
        for (int[] op : operators) {
            int a = op[0];
            if (a == 1){
                int key = op[1];
                int val = op[2];
                set(key, val, k);
            } else {
                int key = op[1];
                int val = get(key);
                list.add(val);
            }
        }
        int[] ans = new int[list.size()];
        int i = 0;
        for (int num : list) {
            ans[i++] = num;
        }
        return ans;
    }

    private void set(int key, int val, int k) {
        if (cache.containsKey(key)) {
            // 更新 value
            Node node = cache.get(key);
            pq.remove(node);
            node.count++;
            node.time = time++;
            node.val = val;

            pq.offer(node);
            
            return;
        } else {
            Node node = new Node(key, val, time++);
            cache.put(key, node);
            if (pq.size() < k) {
                pq.offer(node);
            } else {
                Node peek = pq.poll(); // 去掉一个
                //System.out.println(peek.key  + " " + peek.count + " " + peek.time);
                cache.remove(peek.key);
                pq.offer(node);
            }
        }
    }


    private int get(int key) {
        if (!cache.containsKey(key)) return -1;
        Node node = cache.get(key);
        pq.remove(node);
        node.count++;
        node.time = time++;
        pq.offer(node);
        return node.val;
    }
}