要求

要求实现一个 LRU 缓存器，该缓存器支持两个方法：

  • int get(int key)
  • void set(int key, int value)

时间复杂度为 LRU - 图1

分析

  • 考虑 LRU 的特点：最后一次使用的数据会上浮。可以使用链表来实现这种效果。
  • 考虑写入和读取的时间复杂度，如果使用链表，那么时间复杂度是 LRU - 图2 的；使用散列，可以达到 LRU - 图3 的时间复杂度。
  • 综合使用散列和链表 ，可以在保留 LRU 特性的情况下达到 LRU - 图4 的复杂度。

其逻辑结构如图：
LRU - 图5
注：

  • 使用链表时，用一个伪头部/尾部可以减少很多判断。
  • 这里的链表应该是双向链表，这样才能从中间摘下一个节点，然后放到头部去。