优化LFU缓存最小频率查找的方法有三种：一、双向链表+频率桶映射，维护minFreq变量并动态更新；二、多级最小堆辅助索引，配合freqCount和懒删除；三、单调队列+时间戳标记，利用频率单调性与时间戳验证有效性。

如果您在实现 C++ LFU 缓存时发现频率更新与最小频率查找操作频繁导致时间复杂度退化为 O(n)，则可能是由于每次查询 minFreq 都需遍历所有频率桶。以下是优化最小频率查找的多种实现方法：

一、双向链表 + 频率桶映射

该方法将每个访问频率对应的所有缓存项组织为一个双向链表，并用哈希表记录各频率对应的链表头尾；同时维护一个全局 minFreq 变量，在 put/get 时按需递增，避免全量扫描。

1、定义结构体 Node，包含 key、value、freq 字段，并维护前后指针。

2、使用 unordered_map> freqMap 存储每个频率对应的数据节点链表。

3、使用 unordered_map::iterator> keyMap 存储 key 到对应节点迭代器的映射。

4、在 get 操作中，从 keyMap 获取节点迭代器，将其从原 freq 对应链表中移除，并插入 freq+1 对应链表头部，同时更新 keyMap 中的迭代器位置。

5、在 put 操作中，若缓存已满且 key 不存在，则从 freqMap[minFreq] 的尾部删除节点，并从 keyMap 中擦除对应 key；随后插入新节点到 freqMap[1] 头部，并设置 minFreq = 1。

6、当某次 put 或 get 导致 freqMap[minFreq] 变为空时，执行 minFreq++ 直至 freqMap[minFreq] 非空或超出范围。

二、多级最小堆辅助索引

该方法引入一个小顶堆来动态维护当前所有非空频率值，使 minFreq 查询降至 O(1)，并通过懒删除机制处理频率变更带来的堆不一致问题。

1、声明 priority_queue, greater> minFreqHeap 存储所有当前存在的频率值。

2、使用 unordered_map freqCount 记录每个频率当前对应的有效节点数量。

3、每次需要获取 minFreq 时，持续 pop 堆顶元素直至 freqCount[heapTop] > 0，此时 heapTop 即为真实 minFreq。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

4、在节点频率提升（如 get 或 put 更新）时，将旧 freq 对应的 freqCount 减一，并将新 freq 推入堆中（即使重复也允许）。

5、在插入新节点（put 且 key 不存在）后，将 freq=1 推入堆并令 freqCount[1]++。

6、在删除节点（缓存淘汰）后，对被删节点原 freq 执行 freqCount[freq]--。

三、单调队列 + 时间戳标记

该方法利用插入顺序与频率单调性，在保持 O(1) 平摊 minFreq 查询的同时规避堆的懒删除开销，适用于高吞吐低延迟场景。

1、维护 deque> freqQueue，其中 first 为频率，second 为该频率首次出现的时间戳（递增整数）。

2、每次新节点插入或频率提升时，若当前频率大于队尾频率，则直接 push_back；否则跳过以维持单调递增。

3、使用 unordered_map lastSeen 记录每个频率最后一次被访问的时间戳。

4、在 get 或 put 后更新对应 key 的 freq，并同步更新 lastSeen[freq] = ++timestamp。

5、当需获取 minFreq 时，检查队首 pair 的频率是否仍有效：若 lastSeen[front.first] == 当前该频率最新时间戳，则 front.first 为 minFreq；否则 pop_front。

6、淘汰阶段仅依赖 freqQueue.front().first 获取 minFreq，再从 freqMap[minFreq] 尾部弹出节点。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！