You need to enable JavaScript to run this app. 可快速返回元素位置的LRU缓存O(log(n))实现方案咨询
优惠活动
大模型
产品
解决方案
定价
更多

可快速返回元素位置的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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.22 11:57:02