设计跳表
难度:
标签:
题目描述
不使用任何库函数，设计一个 跳表 。
跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。
了解更多 : https://oi-wiki.org/ds/skiplist/
在本题中，你的设计应该要包含这些函数：
bool search(int target): 返回target是否存在于跳表中。void add(int num): 插入一个元素到跳表。bool erase(int num): 在跳表中删除一个值，如果num不存在，直接返回false. 如果存在多个num，删除其中任意一个即可。
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。
示例 1:
输入 ["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 * 104- 调用
search,add,erase操作次数不大于5 * 104
代码结果
运行时间: 364 ms, 内存: 24.2 MB
/*
* Skiplist implementation using Java Streams
*
* This implementation leverages Java Streams for concise operations
* but note that streams are not typically used for data structure
* manipulation due to their functional nature.
*/
import java.util.*;
class SkiplistStream {
private static final int MAX_LEVEL = 16;
private final Node head = new Node(-1, MAX_LEVEL);
private final Random random = new Random();
private static class Node {
int val;
Node[] forward;
Node(int val, int level) {
this.val = val;
this.forward = new Node[level];
}
}
public boolean search(int target) {
return searchLevel(head, target, MAX_LEVEL - 1);
}
private boolean searchLevel(Node node, int target, int level) {
if (level < 0) return node.forward[0] != null && node.forward[0].val == target;
Node current = node;
while (current.forward[level] != null && current.forward[level].val < target) {
current = current.forward[level];
}
return searchLevel(current, target, level - 1);
}
public void add(int num) {
Node[] update = new Node[MAX_LEVEL];
Node current = head;
for (int i = MAX_LEVEL - 1; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].val < num) {
current = current.forward[i];
}
update[i] = current;
}
int level = randomLevel();
Node newNode = new Node(num, level);
for (int i = 0; i < level; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
public boolean erase(int num) {
Node[] update = new Node[MAX_LEVEL];
Node current = head;
for (int i = MAX_LEVEL - 1; i >= 0; i--) {
while (current.forward[i] != null && current.forward[i].val < num) {
current = current.forward[i];
}
update[i] = current;
}
current = current.forward[0];
if (current == null || current.val != num) {
return false;
}
for (int i = 0; i < MAX_LEVEL; i++) {
if (update[i].forward[i] != current) {
break;
}
update[i].forward[i] = current.forward[i];
}
return true;
}
private int randomLevel() {
int level = 1;
while (random.nextInt(2) == 0 && level < MAX_LEVEL) {
level++;
}
return level;
}
}解释
方法:
跳表是一种可以在对数时间复杂度内进行搜索、添加和删除操作的数据结构。它通过多层链表组织数据，每一层是上一层的子集。在顶层，查找、添加或删除元素时可以跳过大量元素，从而加快速度。代码中实现了一个跳表，包括搜索、添加和删除功能。每个节点存储值和一个列表，列表中的每个元素都指向下一个节点。节点的层数是随机确定的，以确保跳表的效率。
时间复杂度:
O(log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在跳表中，节点的层数是如何决定的？随机层数对跳表性能的影响是什么？
▷🦆
跳表的搜索操作中，为什么需要从最高层开始搜索，而不能从底层或中间某层开始？
▷🦆
在添加节点时，每层的更新逻辑是如何确保跳表的整体结构和效率的？
▷🦆
跳表中的删除操作如何处理节点存在于多层的情况？
▷