题解 | #设计LFU缓存结构 [S-P2]

HashMap + PriorityQueue的时间O(N)解
NOTE: 题目要求O(logN), 还是得双向链表
https://blog.nowcoder.net/n/0c72ed84c3f54959b346cf54273ccfaf

每个elem保存freqeuncy和seq#.
seq#为最近一次对该elem操作的步数id。
PriorityQueue中根据存入elem的[freqeuncy, sequence#]

每次对一个elem进行get或set时跟新该elem的[freqeuncy, sequence#]
并重新插入PQ

set O(N) (i.e. PQ的remove时间为O(N))
get O(N) (i.e. PQ的remove时间为O(N))

import java.util.*;

public class Solution {
  public int[] LFU (int[][] operators, int k) {
    SimpleLFU lfu = new SimpleLFU(k);
    ArrayList<Integer> ans = new ArrayList<>();
      
    for (int[] op : operators) {
      if (op[0] == 1) {
        lfu.set(op[1], op[2]);
      } else {
        ans.add(lfu.get(op[1]));
      }
    }
    
    return ans.stream().mapToInt(i->i).toArray();
  }
}

class SimpleLFU {
  int maxSize;  // k
  int seqNum;   // seq# of operation
  Queue<Elem> minHeap = new PriorityQueue<>(compareElem);
  Map<Integer, Elem> map = new HashMap<>();
  
  class Elem {
    private int key, val;
    private int freq = 0;
    private int seqNum = 0;
    
    Elem(int key, int val) {
      this.key = key;
      this.val = val;
    }
    
    private void touch(int seqNum) {
      this.freq++;
      this.seqNum = seqNum;
    }
    
    @Override
    public String toString() {
      return String.format("%d-%d-%d-%d",
                          key, val, freq, seqNum);
    }
  }
  // order by frequency then seqence#
  private static Comparator<Elem> compareElem = (e1, e2) -> 
    e1.freq == e2.freq ? e1.seqNum - e2.seqNum : e1.freq - e2.freq;
  
  SimpleLFU(int k) {
    this.maxSize = k;
  }
  
  public void set(int key, int val) {
    seqNum++;
    if (!map.containsKey(key)) {
      insert(key, val);
    } else {  // update val
      // remove-update-reinsert
      Elem e = map.get(key);
      minHeap.remove(e);
      e.val = val;
      e.touch(seqNum);
      minHeap.offer(e);
    }
  }
  
  public int get(int key) {
    seqNum++;
    if (!map.containsKey(key))
      return -1;
    
    // remove-update-reinsert
    Elem e = map.get(key);
    minHeap.remove(e);
    e.touch(seqNum);
    minHeap.offer(e);
    return e.val;
  }
  
  private void insert(int key, int val) {
    if (minHeap.size() == maxSize) {
      Elem poped = minHeap.poll();
      map.remove(poped.key);
      // System.out.println("evicted: " + poped);
    }
    
    Elem e = new Elem(key, val);
    e.touch(seqNum);
    map.put(key, e);
    minHeap.offer(e);
  }
}