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

本来想用PriorityQueue，结果超时了，改用俩LinkedHashMap 去存value 和 frequency了。不过代码里还保留了PriorityQueue 的用法，回头看看怎么改进一下时间复杂度。

import java.util.*;
public class Solution {

    public int[] LFU (int[][] operators, int k) {
        // write code here
        if(operators==null||operators.length==0||k<1) return new int[] {-1};
        ArrayList<Integer> res = new ArrayList<>();
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        LinkedHashMap<Integer, Integer> count = new LinkedHashMap<>();
        PriorityQueue<Node> queue = new PriorityQueue<Node>(new Comparator<Node>(){
            public int compare(Node n1, Node n2){
                return n1.frequency - n2.frequency;
            }
        });
        for(int[] op : operators){
            int key = op[1];
            switch(op[0]){
                case 1:
                    if(!map.containsKey(key)){
                        if(map.size()==k){
                            //Node least = queue.poll();
                            //map.remove(least.frequency);
                            int leastkey = getLeast(count);
                            map.remove(leastkey);
                            count.remove(leastkey);
                        }
                        map.put(key,op[2]);
                        count.put(key,1);
                        //Node cur = new Node(key,1);
                        //queue.offer(cur);
                    }else{
                        map.remove(key);
                        map.put(key,op[2]);
                        int fre = count.get(key);
                        count.remove(key);
                        count.put(key,fre+1);
                        //update(queue,key);
                    }
                    break;
                case 2:
                    if(map.containsKey(key)){
                        int value = map.get(key);
                        res.add(value);
                        int fre = count.get(key);
                        count.remove(key);
                        count.put(key,fre+1);
                        //update(queue,key);
                    }else{
                        res.add(-1);
                    }
                    break;
                default:
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    public int getLeast(LinkedHashMap<Integer,Integer> count){
        int min = Integer.MAX_VALUE;
        int key = 0;
        Set<Integer> keyset = count.keySet();
        for(int i : keyset){
            if(count.get(i)<min){
                min = count.get(i);
                key = i;
            }
        }
        return key;
    }

    public void update(Queue<Node> queue, int key){
        Stack<Node> stack = new Stack<Node>();
        while(!queue.isEmpty()){
            Node cur = queue.poll();
            if(cur.key!=key){
                stack.push(cur);
            }else{
                cur.frequency+=1;
                queue.offer(cur);
                break;
            }
        }
        while(!stack.isEmpty()){
            queue.offer(stack.pop());
        }
    }
}

class Node{
    public int key;
    public int frequency;

    public Node(int key, int fre){
        this.key = key;
        this.frequency = fre;
    }
}