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

这题其实跟LRU半斤八两：

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
        ArrayList<Integer> list = new ArrayList<>();
        // int[] 是一个长度为3的数组,第一个元素用来存储value，第二个元素用来存储访问次数
        //，第三个元素记录上次调用的时间
        HashMap<Integer, int[]> map = new HashMap<>(); 

        int counter = 0; // 计时器

        for (int[] operator : operators) {
            if (operator[0] == 1) {
                if (!map.containsKey(operator[1])) {
                    // 如果size等于k, 就要删除一个元素, 此处可以独立出来写一个函数
                    if (map.size() == k) {
                        int rm = 0;
                        int min = Integer.MAX_VALUE;
                        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
                            if (min > entry.getValue()[1]) {
                                rm = entry.getKey();
                                min = entry.getValue()[1];
                            } else {
                                if (entry.getValue()[1] == min) {
                                    if (entry.getValue()[2] < map.get(rm)[2]) {
                                        rm = entry.getKey();
                                    }
                                }
                            }
                        }
                       map.remove(rm);
                    }
                    map.put(operator[1], new int[] {operator[2], 1, counter++});
                } else {
                    map.put(operator[1], new int[] {operator[2], map.get(operator[1])[1] + 1, counter++});
                }
            } else {
                if (map.containsKey(operator[1])) {
                    list.add(map.get(operator[1])[0]);
                    map.get(operator[1])[1]++;
                    map.get(operator[1])[2] = counter++;
                } else {
                    list.add(-1);
                }
            }
        }

        int[] res = new int[list.size()];

        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}