Leetcode:1206. design jump table [jump table board]

analysis

Core data structure
The random height generated by the newly added node
The core traverses from the top to the bottom
Space n, Time logn
Specific implementation reference notes

ac code

MAX_LEVEL = 32 #  The most layers 
P_FACTOR = 0.25 #  The first i There is a node in the layer , The probability of this node on the next level is p, If there is no current layer, there must be no next layer 

def random_level() -> int:
    #  For newly added nodes , Random its lv, Represents it [1,lv] There are pointers 
    lv = 1
    while lv < MAX_LEVEL and random.random() < P_FACTOR:
        lv += 1
    return lv

#  A new hop table node 
class SkiplistNode:
    #  Property slot stuck 
    __slots__ = 'val', 'forward' # forward Indicates the position of the next pointer , Yes max_level layer , Please see the data structure chart for details 

    def __init__(self, val, max_level = MAX_LEVEL):
        self.val = val
        self.forward = [None] * max_level #  Initialize the following pointer 


class Skiplist:

    def __init__(self):
        #  Empty meaningless header node 
        self.head = SkiplistNode(-1)
        #  There are currently no nodes ,0 layer 
        self.level = 0 


    def search(self, target: int) -> bool:
        ''' Each layer finds the closest target But less than target The location of , Go to see No 1 Whether the layers have equal '''
        curr = self.head
        #  Look down from the top 
        for i in range(self.level - 1, -1, -1):
            #  Find No i The layer is smaller than and closest to target The elements of 
            while curr.forward[i] and curr.forward[i].val < target:
                curr = curr.forward[i]
        #  The next one on the last floor will see if it is with target equal 
        curr = curr.forward[0]
        return curr is not None and curr.val == target


    def add(self, num: int) -> None:
        ''' Same as search The search method of , Use the insertion of each layer of linked list to complete '''
        # update Record that each layer is less than and closest to target The elements of , For subsequent updates 
        update = [self.head] * MAX_LEVEL
        curr = self.head
        for i in range(self.level - 1, -1, -1):
            #  Find No i The layer is smaller than and closest to num The elements of 
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            #  Record 
            update[i] = curr
        #  Determine the number of layers of new nodes 
        lv = random_level()
        self.level = max(self.level, lv)
        #  Open point 
        new_node = SkiplistNode(num, lv)

        #  The linked list of each layer is updated , Insertion of linked list 
        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:
        ''' find or Did not find , Deletion of nodes in the linked list '''
        # update Record that each layer is less than and closest to target The elements of , For subsequent updates 
        update = [self.head] * MAX_LEVEL
        curr = self.head
        for i in range(self.level - 1, -1, -1):
            #  Find No i The layer is smaller than and closest to num The elements of 
            while curr.forward[i] and curr.forward[i].val < num:
                curr = curr.forward[i]
            #  Record 
            update[i] = curr
        #  The first 1 Next to the layer , See if there is num
        curr = curr.forward[0]
        if curr is None or curr.val != num: #  non-existent 
            return False
        #  Delete node 
        for i in range(self.level):
            if update[i].forward[i] != curr:
                break
            #  Update from bottom to top , Right. i Update the status of the layer , take forward Point to the next hop of the deleted node 
            update[i].forward[i] = curr.forward[i]
        
        #  Update current level
        while self.level > 1 and self.head.forward[self.level - 1] is None:
            self.level -= 1 #  Remove the empty layer 
        
        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)

summary

Skip the watch board