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

import java.util.*;
class Mark {
    int val;
    int num;
    int time;
    public Mark(int val, int num, int time) {
        this.val = val;
        this.num = num;
        this.time = time;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        Map<Integer, Integer> map = new HashMap<>(k);
        Map<Integer, Mark> mks = new HashMap<>();
        List<Mark> list = new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < operators.length; i++) {
            int[] arr = operators[i];
            if (arr[0] == 1) {
                if (map.containsKey(arr[1])) {
                    map.put(arr[1], arr[2]);
                    Mark m = mks.get(arr[1]);
                    m.num++;
                    m.time = count++;
                } else {
                    if (map.size() >= k) {
                        Collections.sort(list, new Comparator<Mark>() {
                            @Override
                            public int compare(Mark m1, Mark m2) {
                                if (m1.num == m2.num) {
                                    return m1.time - m2.time;
                                }
                                return m1.num - m2.num;

                            }
                        });
                        Mark m = list.get(0);
                        mks.remove(m.val);
                        map.remove(m.val);
                        list.remove(m);
                    }
                    map.put(arr[1], arr[2]);
                    Mark m = new Mark(arr[1], 1, count++);
                    list.add(m);
                    mks.put(arr[1], m);
                }

            } else if (arr[0] == 2) {
                res.add(map.get(arr[1]) == null ? -1 : map.get(arr[1]));
                Mark m = mks.get(arr[1]);
                if (m != null) {
                    m.num++;
                    m.time = count;
                    count++;
                }

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

        return ret;
    }

}