What is the main challenge in implementing LFU Cache?

The primary challenge is updating frequency counts and moving nodes between lists in O(1) time while maintaining accurate pointers for eviction and retrieval.

How do I ensure constant-time get and put operations?

Use a hash map for key lookup and maintain separate doubly-linked lists per frequency, carefully updating pointers when nodes move between lists.

What happens when multiple keys have the same frequency?

Evict the least recently used key among them by removing the tail node from the corresponding frequency list, maintaining LFU order.

Can LFU Cache handle zero capacity?

Yes, but any put operation should be ignored, and get always returns -1, since no keys can be stored.

Why is linked-list pointer manipulation critical for LFU Cache?

It allows constant-time insertion, removal, and frequency updates without traversing lists, which is essential to maintain O(1) complexity.

#460

Hard

auto_awesome链表指针操作

LeetCode 题解工作台

LFU 缓存

请你为最不经常使用（LFU）缓存算法设计并实现数据结构。实现 LFUCache 类： LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象 int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。 void…

哈希表链表设计双向链表

题目描述

请你为最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3

提示：

1 <= capacity <= 10⁴
0 <= key <= 10⁵
0 <= value <= 10⁹
最多调用 2 * 10⁵ 次 get 和 put 方法

lightbulb

解题思路

方法一：双哈希表 + 双向链表

我们定义两个哈希表，其中：

哈希表 $map$ ：用于存储缓存的键值对，哈希表的键 $key$ 对应到缓存节点 $node$ ，方便 $O(1)$ 时间内获取缓存节点。
哈希表 $freqMap$ ：用于存储使用频率相同的缓存节点的双向链表，哈希表的键 $freq$ 对应到双向链表 $list$ ，方便 $O(1)$ 时间内获取使用频率相同的缓存节点的双向链表。

另外，我们还需要维护一个变量 $minFreq$ ，用于记录当前最小的使用频率，方便 $O(1)$ 时间内获取最小使用频率的缓存节点。

对于 $get(key)$ 操作：

我们首先判断 $capacity$ 是否为 $0$ 或者 $map$ 中是否存在键 $key$ ，如果不存在则返回 $-1$ ；否则从 $map$ 中获取缓存节点 $node$ ，并将 $node$ 的使用频率加 $1$ ，最后返回 $node$ 的值。

对于 $put(key, value)$ 操作：

我们首先判断 $capacity$ 是否为 $0$ ，如果为 $0$ 则直接返回；

否则判断 $map$ 中是否存在键 $key$ ，如果存在则从 $map$ 中获取缓存节点 $node$ ，更新 $node$ 的值为 $value$ ，并将 $node$ 的使用频率加 $1$ ，最后返回 $node$ 的值；

如果不存在则判断 $map$ 的长度是否等于 $capacity$ ，如果等于 $capacity$ 则从 $freqMap$ 中获取使用频率最小的双向链表 $list$ ，从 $list$ 中删除最后一个节点，并且移除该节点对应的键值对。然后创建新的缓存节点 $node$ ，将 $node$ 的使用频率设置为 $1$ ，将 $node$ 添加到 $map$ 和 $freqMap$ 中，最后将 $minFreq$ 设置为 $1$ 。

时间复杂度方面，操作 $get$ 和 $put$ 的时间复杂度都是 $O(1)$ 。空间复杂度 $O(n)$ ，其中 $n$ 为缓存的容量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

class Node:
    def __init__(self, key: int, value: int) -> None:
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self) -> None:
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head

    def add_first(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def remove(self, node: Node) -> Node:
        node.next.prev = node.prev
        node.prev.next = node.next
        node.next, node.prev = None, None
        return node

    def remove_last(self) -> Node:
        return self.remove(self.tail.prev)

    def is_empty(self) -> bool:
        return self.head.next == self.tail


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.map = defaultdict(Node)
        self.freq_map = defaultdict(DoublyLinkedList)

    def get(self, key: int) -> int:
        if self.capacity == 0 or key not in self.map:
            return -1
        node = self.map[key]
        self.incr_freq(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.map:
            node = self.map[key]
            node.value = value
            self.incr_freq(node)
            return
        if len(self.map) == self.capacity:
            ls = self.freq_map[self.min_freq]
            node = ls.remove_last()
            self.map.pop(node.key)
        node = Node(key, value)
        self.add_node(node)
        self.map[key] = node
        self.min_freq = 1

    def incr_freq(self, node: Node) -> None:
        freq = node.freq
        ls = self.freq_map[freq]
        ls.remove(node)
        if ls.is_empty():
            self.freq_map.pop(freq)
            if freq == self.min_freq:
                self.min_freq += 1
        node.freq += 1
        self.add_node(node)

    def add_node(self, node: Node) -> None:
        freq = node.freq
        ls = self.freq_map[freq]
        ls.add_first(node)
        self.freq_map[freq] = ls


# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

speed

复杂度分析

指标	值
时间	O(1)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Expect emphasis on linked-list pointer correctness and edge cases.
question_mark
Clarify how frequency counters integrate with hash table nodes.
question_mark
Demonstrate eviction order when multiple keys share the same frequency.

warning

常见陷阱

外企场景

error
Failing to update both the hash map and linked lists on frequency change, leading to inconsistent state.
error
Incorrectly handling eviction when multiple nodes share the lowest frequency.
error
Using a single list for all nodes, which breaks O(1) time guarantees.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement a Most Frequently Used (MFU) cache using the same linked-list pointer manipulation strategy.
arrow_right_alt
Support dynamic resizing of capacity while maintaining O(1) operations.
arrow_right_alt
Track both time-based and frequency-based evictions for hybrid LFU-LRU caches.

help

常见问题

外企场景

继续练习

#432 全 O(1) 的数据结构 #146 LRU 缓存 #355 设计推特