基础数据结构

数据结构设计题

这类题的通用解法

「设计一个 LRU 缓存」「设计一个支持 O(1) 随机取元素的集合」—— 这些题不需要你发明新数据结构。它们考的是一件事：

列出每个操作要求的复杂度，逐个问「什么结构能做到」，然后把它们拼起来。

因为没有哪个单一结构什么都快，答案通常是两个结构的组合，其中一个几乎总是哈希表（负责「按 key 秒找」），另一个负责「维持某种顺序」。

📌 「两个」是常见情况，不是规律。本篇最后那道 LFU 就需要三张表 —— 需要几个，由上面那张需求表决定，不由经验决定。

LRU 缓存：哈希表 + 双链表

题意：固定容量的缓存，get 和 put 都要 O(1)；满了就淘汰最久未使用的。

先拆需求：

操作	要求	谁能做到
按 key 找 value	O(1)	哈希表
把某个元素标记为「最近使用」	O(1)	需要能 O(1) 把它移到一端
淘汰最久未使用的	O(1)	需要能 O(1) 删掉另一端

「维持使用顺序 + 两端 O(1) 操作」→ 双链表。「按 key 找到链表里的那个节点」→ 哈希表存 key → 节点。

🚨 必须是双链表。单链表删除一个节点需要它的前驱，而从哈希表拿到的是节点本身，找前驱要 O(n) —— O(1) 立刻破功。这就是链表那篇说「双链表主要出现在设计题里」的原因。

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();                    // key → 节点
    // ⭐ 哨兵头尾，省掉所有空链表/单元素的边界判断
    this.head = { key: null, val: null };    // head.next 是最近使用的
    this.tail = { key: null, val: null };    // tail.prev 是最久未使用的
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    const node = this.map.get(key);
    if (!node) return -1;
    this._remove(node);        // 摘下来
    this._addToFront(node);    // 挪到最前 = 标记为最近使用
    return node.val;
  }

  put(key, val) {
    const existing = this.map.get(key);
    if (existing) {
      existing.val = val;
      this._remove(existing);
      this._addToFront(existing);
      return;
    }
    if (this.map.size === this.cap) {
      const lru = this.tail.prev;            // 最久未使用
      this._remove(lru);
      this.map.delete(lru.key);              // 🚨 别忘了从 map 里也删
    }
    const node = { key, val };
    this._addToFront(node);
    this.map.set(key, node);
  }
}

🚨 两个高频错误

① 节点里必须存 key。

淘汰时你拿到的是链表尾部的节点，但要从哈希表里删掉它，需要知道它的 key。节点里不存 key 的话，你只能遍历整个 map 去找 —— O(n)，前功尽弃。

⚠️ 这个错的症状很隐蔽：map 只增不减，越来越大，但缓存的读写结果全部正确（链表长度是对的）。表现为内存缓慢泄漏，而不是功能出错。实测 5000 轮 × 40 次操作：

读写结果错的次数        0        ← 功能上完全正常
map 最大涨到           12        ← 而容量上限只有 4

🚨 一次都没错过。对拍测不出来，单元测试测不出来，只有盯着 map.size 才看得见 —— 所以正确版里那句 this.map.delete(lru.key) 值得单独写一条断言：map.size 恒 ≤ 容量。

② 哨兵头尾节点省掉的边界判断比想象中多。

没有哨兵的话，_remove 和 _addToFront 各要处理「链表为空」「操作的是头节点」「操作的是尾节点」三种情况。有了哨兵，node.prev 和 node.next 永远非空，两个方法各两行就写完了。

⭐ 这和链表题里的 dummy 虚拟头结点是同一个技巧，只是用在了两端。

O(1) 插入、删除、随机取：哈希表 + 数组

题意：实现一个集合，insert、remove、getRandom 都是 O(1)。

拆需求：

随机取 → 必须能按下标访问 → 数组
O(1) 判断存在 / 定位 → 哈希表存 值 → 下标
O(1) 删除数组中间的元素 → ⭐ 这一条看起来不可能

数组中间删除是 O(n)，因为后面的要挪。但这里不要求保持顺序 —— 于是有个漂亮的办法：把要删的元素和最后一个交换，然后 pop。

class RandomizedSet {
  constructor() { this.arr = []; this.idx = new Map(); }

  insert(val) {
    if (this.idx.has(val)) return false;
    this.arr.push(val);
    this.idx.set(val, this.arr.length - 1);
    return true;
  }

  remove(val) {
    if (!this.idx.has(val)) return false;
    const i = this.idx.get(val);
    const last = this.arr[this.arr.length - 1];

    this.arr[i] = last;              // 最后一个搬到坑里
    this.idx.set(last, i);           // 🚨 别忘了更新它的下标
    this.arr.pop();
    this.idx.delete(val);
    return true;
  }

  getRandom() { return this.arr[Math.floor(Math.random() * this.arr.length)]; }
}

🚨 this.idx.set(last, i) 不能漏。搬了元素却不更新它在哈希表里的下标，下次删它时会去删错位置。

⚠️ 而且删除自己（val 就是最后一个）时两种写法都正确 —— 因为 idx.delete(val) 紧接着就把那条脏数据清掉了。所以只测「删最后一个」发现不了这个 bug。

📌 顺序也有讲究：idx.set(last, i) 必须在 idx.delete(val) 之前。删的就是最后一个时 last === val，两条语句作用在同一个 key 上，谁后执行谁说了算：

正确顺序   set(7, 0) → delete(7)     idx 干净          ✅
反过来     delete(7) → set(7, 0)     idx 残留 {7: 0}   🚨 而 arr 已经空了

🚨 反过来写的后果不是「记录被删掉」，是「记录该删没删」 —— idx 里留下一条指向已经不存在的元素的脏记录。最小复现只要两步：insert(7); remove(7); 之后 idx.size 仍是 1。

⚠️ 两种错法在随机操作序列上的暴露率（各 20000 轮 × 12 次操作）：

漏掉 idx.set(last, i)    20.8%
两句顺序写反              33.6%

LFU：两个结构不够用的那道题

上面两道题都是「哈希表 + 一个结构」。LFU 是这个套路第一次不够用的地方 —— 值得单独看，因为它暴露了那条套路的边界。

题意和 LRU 只差一个字：淘汰最不经常使用的；频次相同时，才淘汰最久未使用的。

先照第 1 步拆需求：

操作	要求	谁能做到
按 key 找 value	O(1)	哈希表
按 key 找它的频次	O(1)	又一张哈希表
找出当前最小频次里最久未用的那个	O(1)	🚨 这一条是难点

最后一条要求「先按频次分组，组内还要维持使用顺序」。一个结构给不出来，得三张表 + 一个游标：

class LFUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.keyToVal = new Map();       // key → value
    this.keyToFreq = new Map();      // key → 用了几次
    this.freqToKeys = new Map();     // 频次 → Set，⭐ Set 的迭代顺序就是插入顺序
    this.minFreq = 0;                // 当前最小频次，淘汰时直奔这个桶
  }

  // 把 key 的频次 +1，从旧桶挪到新桶
  _bump(key) {
    const f = this.keyToFreq.get(key);
    this.freqToKeys.get(f).delete(key);
    if (this.freqToKeys.get(f).size === 0) {
      this.freqToKeys.delete(f);
      if (this.minFreq === f) this.minFreq++;   // ⭐ 只有空掉的桶正是最小频次，才推进
    }
    this.keyToFreq.set(key, f + 1);
    if (!this.freqToKeys.has(f + 1)) this.freqToKeys.set(f + 1, new Set());
    this.freqToKeys.get(f + 1).add(key);
  }

  get(key) {
    if (!this.keyToVal.has(key)) return -1;
    this._bump(key);
    return this.keyToVal.get(key);
  }

  put(key, val) {
    if (this.cap <= 0) return;
    if (this.keyToVal.has(key)) { this.keyToVal.set(key, val); this._bump(key); return; }

    if (this.keyToVal.size >= this.cap) {
      const bucket = this.freqToKeys.get(this.minFreq);
      const victim = bucket.values().next().value;   // 桶里最早插入的 = 最久未用
      bucket.delete(victim);
      if (bucket.size === 0) this.freqToKeys.delete(this.minFreq);
      this.keyToVal.delete(victim);
      this.keyToFreq.delete(victim);
    }

    this.keyToVal.set(key, val);
    this.keyToFreq.set(key, 1);
    if (!this.freqToKeys.has(1)) this.freqToKeys.set(1, new Set());
    this.freqToKeys.get(1).add(key);
    this.minFreq = 1;                              // 🚨 新元素频次是 1，最小值必然回到 1
  }
}

⭐ 两个关键选择：

freqToKeys 的值用 Set 而不是数组。 JavaScript 的 Set 保证迭代顺序等于插入顺序，于是「桶里第一个」天然就是「组内最久未用的」—— 平局规则不用另写一行代码。删除也是 O(1)，数组的 indexOf + splice 是 O(n)。
minFreq 是个游标，不是算出来的。 每次淘汰都去求最小频次是 O(不同频次数)，而它其实只在两个时刻会变，维护成本 O(1)。

🚨 三种错法，症状完全不同

拿一个照定义写的暴力模型（存频次和时间戳，淘汰时线性扫）对拍，每轮 20 次随机操作、跑 20000 轮。容量和 key 范围会明显改变数字，所以三组都列出来：

错法	症状	cap=2, key 0~4	cap=3, key 0~5	cap=5, key 0~9
A. `put` 末尾漏掉 `minFreq = 1`	全是崩溃	99.3%	94.7%	76.0%
B. 平局时淘汰桶里最后一个	全是答案错	34.6%	37.4%	29.8%
C. `_bump` 里无条件 `minFreq++`	两种都有	75.6%	57.0%	14.9%

⭐ 要记的是「症状」那一列，不是百分比。 三组参数下 A 永远只崩不错、 B 永远只错不崩、C 永远两者都有 —— 这三条是稳的。而百分比浮动很大，C 从 14.9% 到 75.6% 差了五倍。

⚠️ A 和 B 的危险程度正好相反。

A 几乎必然当场崩（TypeError: Cannot read properties of undefined）—— minFreq 指向一个已经被删掉的桶。崩溃很难受但很诚实，一跑就知道。

B 一次都不崩，只是悄悄淘汰错对象。43.4% 的序列结果不同，但每一次调用看起来都正常返回。📌 这类「结果错但不报错」的 bug，是这道题真正的坑 —— 而它恰恰来自一个看起来无关紧要的选择：用数组还是用 Set。

⚠️ 还有一点：容量大到装得下全部 key 时，错法 A 出错率是 0% —— 不是因为它变对了，是因为根本没触发淘汰。

🚨 而且这不只藏起 A：同样的容量下 B 也一次不暴露（20000 轮 0 错 0 崩）。上面三个 bug 全部只在淘汰路径上，容量一给大，整条路径都不会被走到。

cap = 6,  key 0~5      A: 错 0 / 崩 0      B: 错 0 / 崩 0
cap = 10, key 0~5      A: 错 0 / 崩 0      B: 错 0 / 崩 0
cap = 20, key 0~9      A: 错 0 / 崩 0      B: 错 0 / 崩 0

📌 判据：测缓存类的题，容量必须小于 key 的种类数 —— 否则你测的是一个「永远不淘汰的哈希表」。

套路总结

把每个操作和它要求的复杂度列成表
逐行问「什么结构能 O(1) 做到这件事」
没有单一结构能全包 → 组合，哈希表几乎总是其中之一。 表里剩几行搞不定，就还要再加几个结构（LRU 两个，LFU 三个 + 一个游标）
想清楚它们之间怎么互相定位（LRU 是 key→节点，RandomizedSet 是值→下标， LFU 是 key→频次→桶）
🚨 检查每次修改是否每一处都更新了 —— 上面三道题的高频错误全在这一步

⭐ 第 4 步是这类题真正的难点。每个结构各自都简单，难的是维持它们之间那些「指向关系」始终一致 —— 结构从两个变成三个时，要维持的关系从 1 条变成 3 条，这才是 LFU 难在哪里。

练习

勾选记录做过哪些，0 / 5 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

146. LRU 缓存中等哈希表 + 双链表；节点里必须存 key
460. LFU 缓存困难LRU 的进阶，两层映射
380. O(1) 时间插入、删除和获取随机元素中等哈希表 + 数组；和最后一个交换再 pop
706. 设计哈希映射简单手写拉链法
355. 设计推特中等组合已有结构的综合题

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。