可快速返回元素位置的LRU缓存O(log(n))实现方案咨询
压缩K索引问题的O(log n)通用解法
核心需求拆解
你需要维护的结构本质为:
- 一个按最后出现时间从新到旧排序的唯一值列表,队首是最近刚处理过的元素,队尾是最久未处理的元素
- 已存在元素的K值,等于它在该列表中的0起始索引
- 每次处理完任意元素(新值或旧值),都需要将该元素移动到列表队首
- 所有操作要求达到O(log m)时间复杂度,m为当前已出现的唯一值总数
核心数据结构选型
采用带顺序统计能力的平衡二叉搜索树(Order Statistic Tree, OST),这类结构是平衡BST的扩展,每个节点额外存储「以该节点为根的子树总大小」,可在O(log m)时间内完成所有需要的操作:
- 插入任意键值的节点
- 删除任意键值的节点
- 给定键,查询其排名(中序遍历中排在它前面的节点总数,恰好对应列表索引)
- 给定排名,查询对应键值(解压阶段还原值时使用)
不同语言可直接复用成熟实现:C++可使用标准扩展库提供的内置顺序统计树,Java可基于TreeSet扩展实现子树大小维护,无需从零编写平衡树逻辑。
键值映射规则
为了用顺序统计树实现动态列表的维护,给每个唯一值分配一个动态更新的整数键,规则如下:
- 维护全局递减计数器
min_key,初始值设为0,使用64位有符号整数避免溢出 - 新元素插入规则:
- 给新元素分配键值
key = min_key - 1 - 更新
min_key = key - 将
(key, 元素值)的节点插入顺序统计树
- 给新元素分配键值
- 已存在元素移动到队首规则:
- 给该元素分配新键值
key = min_key - 1 - 更新
min_key = key - 删除该元素对应的旧键值节点,插入新键值节点
- 给该元素分配新键值
上述规则下,顺序统计树的升序中序遍历结果,恰好对应「最近到最久的唯一值列表」。某元素的排名(比它键值小的节点总数)就是它的列表索引,即需要输出的K值,完全匹配你给出的示例规则。
完整操作流程
压缩阶段(输入原始数值流,输出N/K前缀序列)
- 额外维护哈希映射
val_to_key:存储每个已出现值对应的当前键值,用于快速定位树中节点 - 逐个处理输入数值
x:- 若
x为新值:- 输出
N{x} - 按新元素规则插入树,更新
val_to_key[x]为新键值
- 输出
- 若
x已存在:- 通过
val_to_key[x]获取当前键值old_key - 查询
old_key对应的排名rank,输出K{rank} - 优化点:若
old_key == min_key(元素已在队首),无需执行删除插入操作;否则按移动规则更新树和映射
- 通过
- 若
解压阶段(输入N/K前缀序列,还原原始数值流)
- 额外维护反向哈希映射
key_to_val:存储每个键值对应的原始数值 - 逐个处理前缀项:
- 若为
N{x}:- 输出
x - 按新元素规则插入树,更新
key_to_val[新键] = x
- 输出
- 若为
K{k}:- 查询排名为
k的节点对应的键值,通过key_to_val得到原始值x,输出x - 优化点:若该值的键值等于
min_key,无需更新树;否则按移动规则更新树和映射
- 查询排名为
- 若为
性能特性
- 所有单步操作时间复杂度均为O(log m),完全规避了经典双向链表LRU实现的O(n)遍历开销
- 64位键值无溢出风险:即使每秒处理100万个新值,可稳定运行超3000年
- 内存开销仅为每个元素存储键值、原始值和子树大小,无额外冗余
内容的提问来源于stack exchange,提问作者Kai Petzke
相关产品推荐
相关产品推荐

