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

哈希表 + 小根堆

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        LFUCache cache = new LFUCache(k);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < operators.length; i++) {
            if (operators[i][0] == 1) {
                cache.set(operators[i][1], operators[i][2]);
            } else {
                ans.add(cache.get(operators[i][1]));
            }
        }
        int[] arr = new int[ans.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = ans.get(i);
        }
        return arr;
    }

    class Node {
        int key;
        int value;
        int times;
        int timestamp;

        public Node(int key, int value, int times, int timestamp) {
            this.key = key;
            this.value = value;
            this.times = times;
            this.timestamp = timestamp;
        }
    }

    class LFUCache {
        int capacity;
        int size;
        int stamp;
        Hashtable<Integer, Node> table;
        PriorityQueue<Node> minHeap;
        public LFUCache(int capacity) {
            table = new Hashtable<>(capacity);
            this.capacity = capacity;
            this.minHeap = new PriorityQueue<>(capacity, (o1, o2) ->
                    o1.times == o2.times ? o1.timestamp - o2.timestamp : o1.times - o2.times);
        }
        public void set(int key, int value) {
            Node node = table.get(key);
            if (node == null) {
                if (size == capacity) {
                    Node remove = minHeap.poll();
                    table.remove(remove.key);
                    size--;
                }
                node = new Node(key, value, 0, stamp++);
                minHeap.add(node);
                table.put(key, node);
                size++;
            } else {
                node.value = value;
                update(node);
            }
        }

        public int get(int key) {
            Node node = table.get(key);
            if (node == null) {
                return -1;
            }
            update(node);
            return node.value;
        }
        private void update(Node node) {
            node.times++;
            node.timestamp = ++stamp;
            heapfy(node);
        }
        private void heapfy(Node node) {
            minHeap.remove(node);
            minHeap.add(node);
        }
    }
}