# LeetCode: 1206. 设计跳表¶

## 1、题目描述¶

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

• bool search(int target) : 返回target是否存在于跳表中。
• void add(int num): 插入一个元素到跳表。
• bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。 了解更多 : https://en.wikipedia.org/wiki/Skip_list

Skiplist skiplist = new Skiplist();

skiplist.search(0);   // 返回 false
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除


• $0 <= num, target <= 20000$
• 最多调用 50000search, add, 以及 erase操作。

## - 设定一个最大的level值，每个节点同时保存当前的level¶

import random
import math

class Node:
def __init__(self, value, levels):
self.value = value
self.levels = [None] * levels

class Skiplist:
max_level = 16

def __init__(self, init_value: int = -1, level: int = None):
self.max_level = self.__class__.max_level if not level else level

def iter_levels(self, target):
for level in range(self.max_level - 1, -1, -1):
while True:
next_node = current.levels[level]
if next_node and next_node.value < target:
current = next_node
else:
break
yield current, level

def search(self, target: int) -> bool:
prev = None
for prev_node, _ in self.iter_levels(target):
prev = prev_node
current_node = prev.levels[0]
return current_node and current_node.value == target

def add(self, num: int) -> None:
# current_level = random.randint(1, self.max_level)
current_level = min(self.max_level, 1 + int(math.log2(1.0 / random.random())))
node = Node(num, current_level)

for prev, prev_level in self.iter_levels(num):
if prev_level < current_level:
next_node = prev.levels[prev_level]
prev.levels[prev_level] = node
node.levels[prev_level] = next_node

def erase(self, num: int) -> bool:
ans = False
for prev, prev_level in self.iter_levels(num):
next_node = prev.levels[prev_level]
if next_node and next_node.value == num:
ans = True
prev.levels[prev_level] = next_node.levels[prev_level]
return ans

# Your Skiplist object will be instantiated and called as such:
# obj = Skiplist()
# param_1 = obj.search(target)