LFU 的全称是 Least Frequently Used(最近不经常使用),是一种缓存淘汰策略,它是根据频率维度来选择将要淘汰的元素,即删除访问频率最低的元素。如果两个元素的访问频率相同,则淘汰最久没被访问的元素。它的底层是 两个哈希表 + N个双链表 实现的,查找和添加的时间复杂度都是O(1)。
460. LFU 缓存
LRU 的全称是 Least Recently Used(最近最少使用),是一种缓存淘汰策略,它是根据时间维度来选择将要淘汰的元素,即删除掉最长时间没被访问的元素据。它的底层是 哈希表 + 双链表 实现的,查找和添加的时间复杂度都是O(1),Java中的LinkedHashMap就是这样的一种数据结构。
LinkedHashMap
剑指 Offer II 031. 最近最少使用缓存
跳表全称叫做跳跃表,本质上就是有序链表 + 多级索引 + 随机技术,它在有序链表上面增加了多级索引,另外采用随机技术来维护数据结构的平衡性。相对于有序链表时间复杂度O(n)而言,跳表的查询、插入、删除的平均时间复杂度都为 O(logn)
采用这种随机技术,跳表中的搜索、插入、删除操作的时间均为O(logn),然而,最坏情况下时间复杂性却变成O(n)。相比之下,在一个有序数组或链表中进行插入/删除操作的时间为O(n),最坏情况下为O(n)。
Leetcode--1206. 设计跳表
上一页
下一页