如果想在 V2EX 获得更好的推广效果，欢迎了解 PRO 会员机制：
https://www.v2ex.com/pro/about

如果你经常使用铜币置顶主题，持有 V2EX Solana Token 会在每日签到时获得额外铜币：
https://www.v2ex.com/solana

This topic created in 2551 days ago, the information mentioned may be changed or developed.

描述

LFU 是一个著名的缓存算法对于容量为 k 的缓存，如果缓存已满，并且需要逐出其中的密钥，则最少使用的密钥将被踢出。实现 LFU 中的 set 和 get

样例

输入:
LFUCache(3)
set(2,2)
set(1,1)
get(2)
get(1)
get(2)
set(3,3)
set(4,4)
get(3)
get(2)
get(1)
get(4)

输出:
2
1
2
-1
2
1
4

解题思路是这个，想说 get 计不计算一次增加 frequency 的操作？能不能言简意赅说一下？

2 replies • 2019-05-27 23:04:02 +08:00

swulling

May 27, 2019 via iPhone

get 肯定算啊，不算缓存的意义就没有了

shawndev

May 27, 2019

如果缓存命中都不能说明 frequency 增加，那还要什么 LFU 淘汰算法