LC 1206. 设计跳表
题目描述
这是 LeetCode 上的 1206. 设计跳表 ，难度为 困难。
不使用任何库函数，设计一个跳表。
跳表 是在 $O(\log{n})$ 时间内完成增加、删除、搜索操作的数据结构。
跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
例如，一个跳表包含 [30, 40, 50, 60, 70, 90]，然后增加 80、45 到跳表中，以下图的方式操作：
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 $O(n)$。
跳表的每一个操作的平均时间复杂度是 $O(\log{n})$，空间复杂度是 $O(n)$。
在本题中，你的设计应该要包含这些函数：
bool search(int target): 返回target是否存在于跳表中。void add(int num): 插入一个元素到跳表。bool erase(int num): 在跳表中删除一个值，如果num不存在，直接返回false. 如果存在多个num，删除其中任意一个即可。
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
示例 1:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]
解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0); // 返回 false
skiplist.add(4);
skiplist.search(1); // 返回 true
skiplist.erase(0); // 返回 false，0 不在跳表中
skiplist.erase(1); // 返回 true
skiplist.search(1); // 返回 false，1 已被擦除
提示:
- $0 <= num, target <= 2 \times 10^4$
- 调用
search,add,erase操作次数不大于 $5 \times 10^4$
数据结构
对于单链表而言，所有的操作（增删改查）都遵循「先查找，再操作」的步骤，这导致在单链表上所有操作复杂度均为 $O(n)$（瓶颈在于查找过程）。
跳表相对于单链表，则是通过引入「多层」链表来优化查找过程，其中每层链表均是「有序」链表：
对于单链表的
Node设计而言，我们只需存储对应的节点值val，以及当前节点的下一节点的指针ne即可（ne为一指针变量）对于跳表来说，除了存储对应的节点值
val以外，我们需要存储当前节点在「每一层」的下一节点指针ne（ne为指针数组）
跳表的 level 编号从下往上递增，最下层的链表为元素最全的有序单链表，而查找过程则是按照 level 从上往下进行。
操作次数的数据范围为 $n = 5 \times 10^4$，因此设计最大的 level 为 $\log{n}$ 即可确保复杂度，但由于操作次数 $n = 5 \times 10^4$ 不可能全是 add 操作，因此这里直接取 level 为 $10$。
同时为了简化，建立一个哨兵节点 he，哨兵值的值应当足够小（根据数据范围，设定为 $-1$ 即可），所有的操作（假设当前操作的传入值为 t），先进行统一化的查找：查找出每一层比 t 严格小的最后一个节点，将其存成 ns 数组。即 $ns[i]$ 为 $level = i$ 层严格比 $t$ 小的最后一个节点。
再根据不同的操作进行下一步动作：
search操作：由于最后一层必然是元素最全的单链表，因此可以直接访问ns[0].ne[0]即是所有元素中满足大于等于t的第一个元素，通过判断其值与传入值t的大小关系来决定结果；add操作：由于最后一层必然是元素最全的单链表，因此我们「从下往上」进行插入，最底下一层必然要插入，然后以一半的概率往上传递；erase操作：与add操作互逆，按照「从下往上」的顺序进行删除。需要注意的是，由于相同的值在跳表中可能存在多个，因此我们在「从下往上」删除过程中需要判断待删除的元素与ns[0].ne[0]是否为同一元素（即要判断地址是否相同，而不是值相同）。
Java 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Skiplist {
int level = 10;
class Node {
int val;
Node[] ne = new Node[level];
Node (int _val) {
val = _val;
}
}
Random random = new Random();
Node he = new Node(-1);
void find(int t, Node[] ns) {
Node cur = he;
for (int i = level - 1; i >= 0; i--) {
while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i];
ns[i] = cur;
}
}
public boolean search(int t) {
Node[] ns = new Node[level];
find(t, ns);
return ns[0].ne[0] != null && ns[0].ne[0].val == t;
}
public void add(int t) {
Node[] ns = new Node[level];
find(t, ns);
Node node = new Node(t);
for (int i = 0; i < level; i++) {
node.ne[i] = ns[i].ne[i];
ns[i].ne[i] = node;
if (random.nextInt(2) == 0) break;
}
}
public boolean erase(int t) {
Node[] ns = new Node[level];
find(t, ns);
Node node = ns[0].ne[0];
if (node == null || node.val != t) return false;
for (int i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i];
return true;
}
}
Python 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Skiplist:
def __init__(self, level=10):
self.level = level
class Node:
def __init__(self, val):
self.val = val
self.ne = [None] * level
self.Node = Node
self.he = Node(-1)
def find(self, t, ns):
cur = self.he
for i in range(self.level - 1, -1, -1):
while cur.ne[i] is not None and cur.ne[i].val < t:
cur = cur.ne[i]
ns[i] = cur
def search(self, t):
ns = [None] * self.level
self.find(t, ns)
return ns[0].ne[0] is not None and ns[0].ne[0].val == t
def add(self, t):
ns = [None] * self.level
self.find(t, ns)
node = self.Node(t)
for i in range(self.level):
node.ne[i] = ns[i].ne[i]
ns[i].ne[i] = node
if random.randint(0, 1) == 0:
break
def erase(self, t):
ns = [None] * self.level
self.find(t, ns)
node = ns[0].ne[0]
if node is None or node.val != t:
return False
for i in range(self.level):
if ns[i].ne[i] == node:
ns[i].ne[i] = ns[i].ne[i].ne[i]
return True
TypeScript 代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41const level: number = 10
class TNode {
val: number
ne: TNode[] = new Array<TNode>(level)
constructor(_val: number) {
this.val = _val
}
}
class Skiplist {
he: TNode = new TNode(-1)
find(t: number, ns: TNode[]): void {
let cur = this.he
for (let i = level - 1; i >= 0; i--) {
while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i]
ns[i] = cur
}
}
search(t: number): boolean {
let ns: TNode[] = new Array<TNode>(level)
this.find(t, ns)
return ns[0].ne[0] != null && ns[0].ne[0].val == t
}
add(t: number): void {
let ns: TNode[] = new Array<TNode>(level)
this.find(t, ns)
const node = new TNode(t)
for (let i = 0; i < level; i++) {
node.ne[i] = ns[i].ne[i]
ns[i].ne[i] = node
if (Math.round(Math.random()) == 0) break
}
}
erase(t: number): boolean {
let ns: TNode[] = new Array<TNode>(level)
this.find(t, ns)
const node = ns[0].ne[0]
if (node == null || node.val != t) return false
for (let i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i]
return true
}
}
- 时间复杂度：所有操作的复杂度瓶颈在于
find查找，find查找期望复杂度为 $O(\log{n})$ - 空间复杂度：$O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1206 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！
