当前位置：首页 > news >正文

面试官问LFU缓存，我用C++手撕了一个O(1)实现（附LeetCode 460题解）

news 2026/4/19 18:04:57

面试官问LFU缓存，我用C++手撕了一个O(1)实现（附LeetCode 460题解）

在技术面试中，缓存淘汰算法是考察候选人数据结构与算法能力的热门话题。当面试官从LRU过渡到LFU时，往往期待看到候选人对时间复杂度与空间复杂度的精准把控。本文将分享如何用双哈希表+多双向链表实现真正的O(1)时间复杂度LFU缓存，并附上面试现场可复用的代码模板。

1. 理解LFU算法的核心挑战

LFU（Least Frequently Used）淘汰策略需要同时考虑访问频率和访问时序两个维度。与LRU单纯依赖时间维度不同，LFU在频率相同的情况下才会启用LRU策略。这种双重标准带来了实现上的独特挑战：

频率维度：需要快速定位当前最低频率
时序维度：相同频率下需要维护访问时间顺序
动态更新：每次访问都会改变节点的频率属性

传统实现若使用优先队列维护频率，put/get操作会退化为O(logN)时间复杂度。而面试官期待的O(1)实现需要更精巧的数据结构设计。

2. 双哈希表+多双向链表结构设计

实现O(1)时间复杂度的关键在于建立两层映射关系：

// 第一层哈希：键到节点的映射 unordered_map<int, Node*> keyToNode; // 第二层哈希：频率到双向链表的映射 unordered_map<int, FreqList*> freqToList;

每个频率值对应一个独立双向链表，节点按访问时间排序。这种结构带来三个核心优势：

O(1)访问节点：通过keyToNode直接定位
O(1)更新频率：节点从一个频率链表移除后立即加入新频率链表
O(1)淘汰节点：始终通过minFreq访问最低频率链表头部

3. 关键数据结构实现细节

3.1 节点与链表定义

struct Node { int key, value, freq; Node *prev, *next; Node(int k, int v, int f): key(k), value(v), freq(f), prev(nullptr), next(nullptr) {} }; struct FreqList { int freq; Node *dummyHead, *dummyTail; FreqList(int f): freq(f) { dummyHead = new Node(-1, -1, f); dummyTail = new Node(-1, -1, f); dummyHead->next = dummyTail; dummyTail->prev = dummyHead; } void addToTail(Node* node) { node->prev = dummyTail->prev; node->next = dummyTail; dummyTail->prev->next = node; dummyTail->prev = node; } void removeNode(Node* node) { node->prev->next = node->next; node->next->prev = node->prev; } bool isEmpty() { return dummyHead->next == dummyTail; } };

3.2 维护minFreq的技巧

minFreq的维护是面试中最容易忽略的关键点：

void updateMinFreq() { while (freqToList.find(minFreq) == freqToList.end() || freqToList[minFreq]->isEmpty()) { minFreq++; } }

当某个频率链表变空时，minFreq需要递增。这种惰性更新策略保证了O(1)时间复杂度。

4. 完整实现与LeetCode 460题解

以下是可以通过LeetCode 460的完整实现，包含详细的注释说明：

class LFUCache { private: int capacity; int minFreq; unordered_map<int, Node*> keyToNode; unordered_map<int, FreqList*> freqToList; void addNode(Node* node) { int freq = node->freq; if (freqToList.find(freq) == freqToList.end()) { freqToList[freq] = new FreqList(freq); } freqToList[freq]->addToTail(node); } void removeNode(Node* node) { freqToList[node->freq]->removeNode(node); if (freqToList[node->freq]->isEmpty()) { delete freqToList[node->freq]; freqToList.erase(node->freq); } } void updateMinFreq() { while (freqToList.find(minFreq) == freqToList.end() || freqToList[minFreq]->isEmpty()) { minFreq++; } } public: LFUCache(int capacity) { this->capacity = capacity; minFreq = 1; } int get(int key) { if (keyToNode.find(key) == keyToNode.end()) { return -1; } Node* node = keyToNode[key]; removeNode(node); node->freq++; addNode(node); updateMinFreq(); return node->value; } void put(int key, int value) { if (capacity == 0) return; if (get(key) != -1) { keyToNode[key]->value = value; return; } if (keyToNode.size() == capacity) { Node* toRemove = freqToList[minFreq]->dummyHead->next; keyToNode.erase(toRemove->key); removeNode(toRemove); delete toRemove; } Node* newNode = new Node(key, value, 1); keyToNode[key] = newNode; addNode(newNode); minFreq = 1; } };