LeetCode 1206. 设计跳表
目录
题目描述
题意分析
要交付的是一个有序多重集合，对外只暴露三个动作：
search(target)回答某个值在不在，add(num)放进一个值，erase(num)拿走一个值并回答有没有拿到。注意是「多重」集合，同一个值可以被add多次，erase一次只需要拿走其中一个，剩下的副本必须还在。约束里有三个信号。第一个是题面明写的「不使用任何库函数」，这直接封死了
TreeSet、TreeMap这类现成有序容器，意思是要求手写数据结构本身。第二个是值域0 <= num, target <= 2 * 10^4很窄，窄到可以开一个长度 20001 的计数桶把三个操作都做成 $O(1)$——但那是钻值域的空子，一旦面试官把值域换成int全域就整个失效，所以它是个诱饵而不是答案。第三个是操作总次数上限 $5 \times 10^4$，这个量级配合「有序容器」的要求，指向的是单次操作 $O(\log n)$ 的结构，同时也框定了结构最多需要多少层索引。
erase要返回布尔值这一点也值得单独拎出来：它意味着删除必须「先确认存在再动手」，不能盲改指针，因此删除天然要复用一次完整的查找。边界情形：容器为空时
search与erase都要安全地返回false而不是空指针；删一个从来没插入过的值返回false；插入的值可能小于当前所有元素或大于当前所有元素，接在最前和接在最后都要成立；同一个值插入多次后连续删除多次，每次都应该成功，直到副本用完才返回false。
解法：多层有序链表 + 前驱数组
核心思路
有序链表插入、删除指针很便宜，但查找需要线性扫描。跳表在底层链表之上增加多级稀疏索引：查找从最高层开始，能向右就尽量向右，不能再走时下降一层，直到最底层。它相当于用链表模拟二分查找的“大步跳跃”。
高层节点通过随机层高产生。节点至少有 1 层；每次以二分之一概率再升一层，因此高一层的节点数期望减半，层数期望为 $O(\log n)$。随机化免去了平衡树的旋转或重平衡，但复杂度是期望保证，极端情况下仍可能退化为链表。
插入和删除的关键不是找到目标本身，而是找到目标在每一层的前驱。定义
update[i]为第i层最后一个值严格小于target的节点。一次自顶向下查找即可填好整个update数组：
search检查update[0].next[0]是否等于目标；add在新节点覆盖的每一层，把它插入update[i]后面；erase找到最底层第一个目标节点，并从它实际出现的各层摘除。每层都保持有序，高层链表始终是低层链表的子序列。下降时无需回到头节点，正是因为当前节点也存在于下一层。
解题步骤
- 创建覆盖
MAX_LEVEL层的头哨兵，当前有效层数初始为 1。- 查找前驱时，从当前最高层开始；右侧节点值小于目标就右移，否则记录当前节点并下降一层。
search查看最底层前驱的后继是否等于目标。add随机生成节点层高；若超过当前层数，新层的前驱只能是头哨兵。随后逐层执行“新节点接旧后继、前驱接新节点”。erase先确认最底层目标存在，再从该节点拥有的各层断开它；最后收缩已经为空的最高层。重复值会被插在已有相同值之前。
erase每次只摘掉一个具体节点，因此重复插入两次后，必须连续删除两次才会彻底消失。
代码实现
import java.util.concurrent.ThreadLocalRandom;
class Skiplist {
private static final int MAX_LEVEL = 32;
private final Node head = new Node(-1, MAX_LEVEL);
private int level = 1;
public boolean search(int target) {
Node candidate = findPredecessors(target)[0].next[0];
return candidate != null && candidate.value == target;
}
public void add(int num) {
Node[] update = findPredecessors(num);
int nodeLevel = randomLevel();
if (nodeLevel > level) {
for (int i = level; i < nodeLevel; i++) {
update[i] = head;
}
level = nodeLevel;
}
Node node = new Node(num, nodeLevel);
for (int i = 0; i < nodeLevel; i++) {
node.next[i] = update[i].next[i];
update[i].next[i] = node;
}
}
public boolean erase(int num) {
Node[] update = findPredecessors(num);
Node target = update[0].next[0];
if (target == null || target.value != num) {
return false;
}
for (int i = 0; i < target.next.length; i++) {
update[i].next[i] = target.next[i];
}
while (level > 1 && head.next[level - 1] == null) {
level--;
}
return true;
}
private Node[] findPredecessors(int target) {
Node[] update = new Node[MAX_LEVEL];
Node current = head;
for (int i = level - 1; i >= 0; i--) {
while (current.next[i] != null && current.next[i].value < target) {
current = current.next[i];
}
update[i] = current;
}
return update;
}
private int randomLevel() {
int nodeLevel = 1;
while (nodeLevel < MAX_LEVEL && ThreadLocalRandom.current().nextBoolean()) {
nodeLevel++;
}
return nodeLevel;
}
private static class Node {
final int value;
final Node[] next;
Node(int value, int level) {
this.value = value;
this.next = new Node[level];
}
}
}
import "math/rand"
const maxSkipLevel = 32
type skipNode struct {
value int
next []*skipNode
}
type Skiplist struct {
head *skipNode
level int
}
func Constructor() Skiplist {
return Skiplist{
head: &skipNode{value: -1, next: make([]*skipNode, maxSkipLevel)},
level: 1,
}
}
func (s *Skiplist) Search(target int) bool {
candidate := s.findPredecessors(target)[0].next[0]
return candidate != nil && candidate.value == target
}
func (s *Skiplist) Add(num int) {
update := s.findPredecessors(num)
nodeLevel := randomLevel()
if nodeLevel > s.level {
for i := s.level; i < nodeLevel; i++ {
update[i] = s.head
}
s.level = nodeLevel
}
node := &skipNode{value: num, next: make([]*skipNode, nodeLevel)}
for i := 0; i < nodeLevel; i++ {
node.next[i] = update[i].next[i]
update[i].next[i] = node
}
}
func (s *Skiplist) Erase(num int) bool {
update := s.findPredecessors(num)
target := update[0].next[0]
if target == nil || target.value != num {
return false
}
for i := 0; i < len(target.next); i++ {
update[i].next[i] = target.next[i]
}
for s.level > 1 && s.head.next[s.level-1] == nil {
s.level--
}
return true
}
func (s *Skiplist) findPredecessors(target int) []*skipNode {
update := make([]*skipNode, maxSkipLevel)
current := s.head
for i := s.level - 1; i >= 0; i-- {
for current.next[i] != nil && current.next[i].value < target {
current = current.next[i]
}
update[i] = current
}
return update
}
func randomLevel() int {
level := 1
for level < maxSkipLevel && rand.Intn(2) == 1 {
level++
}
return level
}
复杂度分析
- 时间复杂度：
search、add、erase的期望时间均为 $O(\log n)$；随机层高极端失衡时最坏为 $O(n)$。- 空间复杂度：期望 $O(n)$。各层节点数构成等比级数，平均每个节点只有常数条前进指针；一次操作的
update固定最多 32 项。
关键点总结
- 查找路径始终是“当前层尽量向右，不能走就下降”，且下降时不回头。
update[i]保存每层前驱，让一次查找同时服务插入和删除。- 前驱比较必须严格小于目标，才能让最底层后继停在第一个目标值上。
- 随机层高使高层节点数量按比例衰减，换来期望 $O(\log n)$，但没有最坏情况平衡保证。
- 节点可以重复；删除的是一个节点，不是删除所有相同值。
易错点总结
- 前驱查找写成
<= target会越过所有目标节点，导致查询和删除失败。- 插入时必须先让新节点指向旧后继，再让前驱指向新节点；顺序反了会形成自环。
- 新节点层高超过当前有效层数时，新增各层的前驱要补成头哨兵。
- 删除只能修改目标节点实际存在的层，否则会访问越界或误删其他链路。
- 删除最高层最后一个节点后要收缩
level，但至少保留第 0 层。- 把复杂度说成严格 $O(\log n)$ 不准确；跳表依赖随机分布，只能给出期望保证。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 707. 设计链表 | 中等 | 跳表的单层退化版，只需按下标定位，是练习哑节点与指针改接的入门题 |
| 146. LRU 缓存 | 中等 | 同样是哈希表配链表，但维护的是访问时间顺序而非值序，靠双向链表 O(1) 摘节点 |
| 460. LFU 缓存 | 困难 | 在 LRU 之上再按频次分桶，需要两层索引结构，是设计题里指针最密的一道 |
| 295. 数据流的中位数 | 困难 | 同样要动态维护有序性，但只关心中位，用对顶堆比完整有序结构更省 |
| 703. 数据流中的第 K 大元素 | 简单 | 动态插入加定序查询的最简形式，固定大小的小顶堆即可 |
| 208. 实现 Trie (前缀树) | 中等 | 同为多层索引结构，但分叉依据是字符而非概率层高 |
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 放弃有序性换取 O(1)，用数组加哈希表的尾部交换删除法 |
| 622. 设计循环队列 | 中等 | 定容结构设计，考点在头尾下标取模与空满判别 |
| 1472. 设计浏览器历史记录 | 中等 | 需要前后跳转的设计题，双栈或数组加下标都可，重点是边界裁剪 |