学习：
# 作者：力扣官方题解; Python
MAX_LEVEL = 32
P_FACTOR = 0.25
def random_level() -> int:
lv = 1
while lv < MAX_LEVEL and random.random() < P_FACTOR:
lv += 1
return lv
class SkiplistNode:
__slots__ = 'val', 'forward'
def __init__(self, val: int, max_level=MAX_LEVEL):
self.val = val
self.forward = [None] * max_level
class Skiplist:
def __init__(self):
self.head = SkiplistNode(-1)
self.level = 0
def search(self, target: int) -> bool:
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 target 的元素
while curr.forward[i] and curr.forward[i].val < target:
curr = curr.forward[i]
curr = curr.forward[0]
# 检测当前元素的值是否等于 target
return curr is not None and curr.val == target
def add(self, num: int) -> None:
update = [self.head] * MAX_LEVEL
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 num 的元素
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
lv = random_level()
self.level = max(self.level, lv)
new_node = SkiplistNode(num, lv)
for i in range(lv):
# 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点
new_node.forward[i] = update[i].forward[i]
update[i].forward[i] = new_node
def erase(self, num: int) -> bool:
update = [None] * MAX_LEVEL
curr = self.head
for i in range(self.level - 1, -1, -1):
# 找到第 i 层小于且最接近 num 的元素
while curr.forward[i] and curr.forward[i].val < num:
curr = curr.forward[i]
update[i] = curr
curr = curr.forward[0]
if curr is None or curr.val != num: # 值不存在
return False
for i in range(self.level):
if update[i].forward[i] != curr:
break
# 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳
update[i].forward[i] = curr.forward[i]
# 更新当前的 level
while self.level > 1 and self.head.forward[self.level - 1] is None:
self.level -= 1
return True
据说 p = 0.5 表现显著优于官方解答、并不用update的版本：
class Skiplist {
public:
Skiplist() : level(0), dummy(new Node(-1)) {
}
bool search(int target) {
auto cur = dummy;
for (int i = level; i >= 0; --i) {
while (cur->next[i] && cur->next[i]->v < target) cur = cur->next[i];
}
return cur->next[0] && cur->next[0]->v == target;
}
void add(int num) {
int h = getHeight();
auto node = new Node(num, h + 1);
level = max(level, h);
auto cur = dummy;
for (int i = level; i >= 0; --i) {
while (cur->next[i] && cur->next[i]->v < num) cur = cur->next[i];
if (i <= h) {
auto next = cur->next[i];
cur->next[i] = node;
node->next[i] = next;
}
}
}
bool erase(int num) {
auto cur = dummy;
Node* target = nullptr;
for (int i = level; i >= 0; --i) {
while (cur->next[i] && cur->next[i]->v < num) cur = cur->next[i];
while (target && cur->next[i] != target) cur = cur->next[i];
if (cur->next[i] && cur->next[i]->v == num) {
target = cur->next[i];
cur->next[i] = target->next[i];
}
}
if (target && target->next.size() == level + 1) {
while (level && !dummy->next[level]) --level;
}
delete target;
return target;
}
private:
int getHeight() {
for (int i = 0; i < MAX_LEVEL; ++i) {
if ((rand() & 1) == 0) return i;
}
return MAX_LEVEL - 1;
}
int level;
const static int MAX_LEVEL = 16;
struct Node {
int v;
vector<Node*> next;
Node(int num, int lv = MAX_LEVEL) : v(num), next(lv) {}
};
Node* dummy;
};
// 作者：力扣官方题解; C++
constexpr int MAX_LEVEL = 32;
constexpr double P_FACTOR = 0.25;
struct SkiplistNode {
int val;
vector<SkiplistNode *> forward;
SkiplistNode(int _val, int _maxLevel = MAX_LEVEL) : val(_val), forward(_maxLevel, nullptr) {
}
};
class Skiplist {
private:
SkiplistNode * head;
int level;
mt19937 gen{random_device{}()};
uniform_real_distribution<double> dis;
public:
Skiplist(): head(new SkiplistNode(-1)), level(0), dis(0, 1) {
}
bool search(int target) {
SkiplistNode *curr = this->head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 target 的元素*/
while (curr->forward[i] && curr->forward[i]->val < target) {
curr = curr->forward[i];
}
}
curr = curr->forward[0];
/* 检测当前元素的值是否等于 target */
if (curr && curr->val == target) {
return true;
}
return false;
}
void add(int num) {
vector<SkiplistNode *> update(MAX_LEVEL, head);
SkiplistNode *curr = this->head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr->forward[i] && curr->forward[i]->val < num) {
curr = curr->forward[i];
}
update[i] = curr;
}
int lv = randomLevel();
level = max(level, lv);
SkiplistNode *newNode = new SkiplistNode(num, lv);
for (int i = 0; i < lv; i++) {
/* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
}
bool erase(int num) {
vector<SkiplistNode *> update(MAX_LEVEL, nullptr);
SkiplistNode *curr = this->head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr->forward[i] && curr->forward[i]->val < num) {
curr = curr->forward[i];
}
update[i] = curr;
}
curr = curr->forward[0];
/* 如果值不存在则返回 false */
if (!curr || curr->val != num) {
return false;
}
for (int i = 0; i < level; i++) {
if (update[i]->forward[i] != curr) {
break;
}
/* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
update[i]->forward[i] = curr->forward[i];
}
delete curr;
/* 更新当前的 level */
while (level > 1 && head->forward[level - 1] == nullptr) {
level--;
}
return true;
}
int randomLevel() {
int lv = 1;
/* 随机生成 lv */
while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {
lv++;
}
return lv;
}
};
