leetcode：1206. 设计跳表【跳表板子】

分析

核心数据结构
新加入节点生成的随机高度
核心的从头遍历从最高层往下找
空间n，时间logn
具体实现参考注释

ac code

MAX_LEVEL = 32 # 最多的层数
P_FACTOR = 0.25 # 第i层有某个节点，下一层还有这个节点的概率是p，若当前层没有下一层必然也没有

def random_level() -> int:
    # 对新加入的节点，随机它的lv，代表着它[1,lv]都存在指针
    lv = 1
    while lv < MAX_LEVEL and random.random() < P_FACTOR:
        lv += 1
    return lv

# 一个新的跳表节点
class SkiplistNode:
    # 属性槽卡住
    __slots__ = 'val', 'forward' # forward表示下一个指针的位置，有max_level层，详细请看数据结构图

    def __init__(self, val, max_level = MAX_LEVEL):
        self.val = val
        self.forward = [None] * max_level # 初始化后面的指针


class Skiplist:

    def __init__(self):
        # 空的无意义的头节点
        self.head = SkiplistNode(-1)
        # 当前没有节点，0层
        self.level = 0 


    def search(self, target: int) -> bool:
        '''每层找到最接近target但小于target的位置，去看第1层有无相等的'''
        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]
        # 最后一层的下一个看看是否和target相等
        curr = curr.forward[0]
        return curr is not None and curr.val == target


    def add(self, num: int) -> None:
        '''同search的搜索方法，利用每层链表的插入完成'''
        # update记录每层小于且最接近target的元素，便于后续更新
        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):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node


    def erase(self, num: int) -> bool:
        '''找到or没找到，链表中节点的删除'''
        # update记录每层小于且最接近target的元素，便于后续更新
        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
        # 第1层的下一个，看看是否存在num
        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




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

总结

跳表板子