# 数据结构与算法--LFU算法

# 一、简介

LFU 的全称是 Least Frequently Used(最近不经常使用)，是一种缓存淘汰策略，它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。它的底层是 两个哈希表 + N个双链表 实现的，查找和添加的时间复杂度都是O(1)。

460. LFU 缓存

# 数据结构与算法--LRU算法

# 一、简介

LRU 的全称是 Least Recently Used(最近最少使用)，是一种缓存淘汰策略，它是根据时间维度来选择将要淘汰的元素，即删除掉最长时间没被访问的元素据。它的底层是 哈希表 + 双链表 实现的，查找和添加的时间复杂度都是O(1)，Java中的LinkedHashMap就是这样的一种数据结构。

剑指 Offer II 031. 最近最少使用缓存

# 数据结构与算法--跳表

# 一、简介

跳表全称叫做跳跃表，本质上就是有序链表 + 多级索引 + 随机技术，它在有序链表上面增加了多级索引，另外采用随机技术来维护数据结构的平衡性。相对于有序链表时间复杂度O(n)而言，跳表的查询、插入、删除的平均时间复杂度都为 O(logn)

采用这种随机技术，跳表中的搜索、插入、删除操作的时间均为O(logn)，然而，最坏情况下时间复杂性却变成O(n)。相比之下，在一个有序数组或链表中进行插入/删除操作的时间为O(n)，最坏情况下为O(n)。

Leetcode--1206. 设计跳表