【Day 91 】2023-05-15 - 1206. 设计跳表

[azl397985856]

1206. 设计跳表

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/design-skiplist/

前置知识

暂无

题目描述

不使用任何库函数，设计一个跳表。

跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

例如，一个跳表包含 [30, 40, 50, 60, 70, 90]，然后增加 80、45 到跳表中，以下图的方式操作：

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

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

在本题中，你的设计应该要包含这些函数：

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.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 <= 20000
最多调用 50000 次 search, add, 以及 erase操作。

[lp1506947671]

class Skiplist:

    def __init__(self):
        left = [Node(-1) for _ in range(16)]
        right = [Node(20001) for _ in range(16)]
        for i in range(15):
            left[i].right = right[i]
            left[i].down = left[i + 1]
            right[i].down = right[i + 1]
        left[-1].right = right[-1]
        self.root = left[0]

    def search(self, target: int) -> bool:
        cur = self.root
        while cur:
            if target < cur.right.val: # in range
                cur = cur.down
            elif target > cur.right.val: # next range
                cur = cur.right
            else:
                return True
        return False

    def add(self, num: int) -> None:
        cur = self.root
        stack = []
        while cur:
            if cur.right.val >= num:
                stack.append(cur)
                cur = cur.down
            else:
                cur = cur.right
        pre = None

        while stack:
            cur = stack.pop()
            node = Node(num)
            node.right = cur.right
            cur.right = node
            if pre:
                node.down = pre
            pre = node
            if random.randint(0, 1):
                break

    def erase(self, num: int) -> bool:
        cur = self.root
        removed = False
        while cur:
            if num < cur.right.val:
                cur = cur.down
            elif num > cur.right.val:
                cur = cur.right
            else:
                cur.right = cur.right.right
                removed = True
                cur = cur.down # remove all down
        return removed

class Node:
    def __init__(self, val=0, right=None, down=None):
        self.val = val
        self.right = right
        self.down = down

[NorthSeacoder]

class Node {
    constructor(val = null, next = null, down = null) {
        this.val = val;
        this.next = next;
        this.down = down;
    }
}
var Skiplist = function () {
    this.head = new Node();
};

/** 
 * @param {number} target
 * @return {boolean}
 */
Skiplist.prototype.search = function (target) {
    let cur = this.head;
    while (cur) {
        while (cur.next && cur.next.val < target) {
            cur = cur.next
        }
        if (!cur.next || cur.next.val > target) {
            cur = cur.down
        } else {
            return true
        }
    }
    return false
};

/** 
 * @param {number} num
 * @return {void}
 */
Skiplist.prototype.add = function (num) {
    const stack = [];
    let cur = this.head;
    while (cur) {
        while (cur.next && cur.next.val < num) cur = cur.next;
        stack.push(cur);
        cur = cur.down
    }
    let needInsert = true, downNode = null;
    while (needInsert && stack.length) {
        let pre = stack.pop();
        pre.next = new Node(num, pre.next, downNode);
        downNode = pre.next;
        needInsert = Math.random() < 0.5
    }

    if (needInsert) {
        this.head = new Node(null, new Node(num, null, downNode), this.head)
    }
};

/** 
 * @param {number} num
 * @return {boolean}
 */
Skiplist.prototype.erase = function (num) {
    let head = this.head;
    let seen = false;

    while (head) {
        while (head.next && head.next.val < num) head = head.next;
        if (!head.next || head.next.val > num) head = head.down;
        else {
            seen = true
            head.next = head.next.next
            head = head.down
        }
    }

    return seen;
};

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

[RestlessBreeze]

code

class Skiplist 
{
public:
    static const int level = 8; 

    struct Node 
    {
        int val; 
        vector<Node*> next; 
        Node(int _val) : val(_val) 
        { 
            next.resize(level, NULL); 
        }
    }*head;

    Skiplist() 
    {
        head = new Node(-1);
    }

    ~Skiplist() 
    {
        delete head; 
    }

    void find(int target, vector<Node*>& pre) 
    {
        auto p = head;
        for (int i = level - 1; i >= 0; i -- ) 
        { 
            while (p->next[i] && p->next[i]->val < target) p = p->next[i]; 
            pre[i] = p; 
        }
    }

    bool search(int target) 
    {
        vector<Node*> pre(level);
        find(target, pre); 

        auto p = pre[0]->next[0]; 
        return p && p->val == target;
    }

    void add(int num) 
    {
        vector<Node*> pre(level);
        find(num, pre); 

        auto p = new Node(num); 
        for (int i = 0; i < level; i ++ ) 
        { 
            p->next[i] = pre[i]->next[i]; 
            pre[i]->next[i] = p;
            if (rand() % 2) 
                break; 
        }
    }

    bool erase(int num) 
    {
        vector<Node*> pre(level);
        find(num, pre); 

        auto p = pre[0]->next[0];
        if (!p || p->val != num) 
            return false;

        for (int i = 0; i < level && pre[i]->next[i] == p; i ++ ) 
        {
            pre[i]->next[i] = p->next[i];
        }

        delete p;
        return true;
    }
};

/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist* obj = new Skiplist();
 * bool param_1 = obj->search(target);
 * obj->add(num);
 * bool param_3 = obj->erase(num);
 */

[Zoeyzyzyzy]

class Skiplist {
    int level = 10;
    class Node {
        int val;
        Node[] ne = new Node[level];
        Node (int _val) {
            val = _val;
        }
    }
    Random random = new Random();
    Node he = new Node(-1);
    void find(int t, Node[] ns) {
        Node cur = he;
        for (int i = level - 1; i >= 0; i--) {
            while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i];
            ns[i] = cur;
        }
    }
    public boolean search(int t) {
        Node[] ns = new Node[level];
        find(t, ns);
        return ns[0].ne[0] != null && ns[0].ne[0].val == t;
    }
    public void add(int t) {
        Node[] ns = new Node[level];
        find(t, ns);
        Node node = new Node(t);
        for (int i = 0; i < level; i++) {
            node.ne[i] = ns[i].ne[i];
            ns[i].ne[i] = node;
            if (random.nextInt(2) == 0) break;
        }
    }
    public boolean erase(int t) {
        Node[] ns = new Node[level];
        find(t, ns);
        Node node = ns[0].ne[0];
        if (node == null || node.val != t) return false;
        for (int i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i];
        return true;
    }
}

[Diana21170648]

思路

跳表初始化，增删差,为了减少查找链表增加比较次数，而产生跳表

class Skiplist:

    def __init__(self):
        left=[Node(-1) for _ in range(16)]
        right=[Node(20001) for _ in range(16)]
        for i in range(15):
            left[i].right=right[i]
            left[i].down=left[i+1]
            right[i].down=right[i+1]
        left[-1].right=right[-1]
        self.root=left[0]

    def search(self, target: int) -> bool:
        cur=self.root
        while cur:
            if target<cur.right.val:
                cur=cur.down
            elif target>cur.right.val:
                cur=cur.right
            else:
                return True
        return False    

    def add(self, num: int) -> None:
        cur=self.root
        stack=[]
        while cur:
            if cur.right.val>=num:
                stack.append(cur)
                cur=cur.down
            else:
                cur=cur.right
        pre=None
        while stack:
            cur=stack.pop()
            Node=Node(num)
            node.right=cur.right
            cur.right=node
        if pre:
            node.down=pre
        pre=node
        if random.randint(0,1):
            break

    def erase(self, num: int) -> bool:
        cur=self.root
        removed=False
        while cur:
            if num<cur.right.val:
                cur=cur.down
            elif num>cur.right.val:
                cur=cur.right
            else:
                cur.right=cur.right.right
                remove=True
                cur=cur.down
        return removed
class Node:
    def __init__(self,val=0,right=None,down=None):
        self.val=val
        self.right=right
        self.down=down

**复杂度分析**
- 时间复杂度：O(logN)，其中 N 为数组长度。
- 空间复杂度：O(N)

[zhangyu1131]

const int MAX_LEVEL = 32;

struct SkiplistNode
{
    int val;
    vector<SkiplistNode*> next; // 多层next节点

    SkiplistNode(int val, int level_cnt = MAX_LEVEL) : val(val), next(level_cnt, nullptr) {}
};

class Skiplist {
public:
    Skiplist() : head(new SkiplistNode(-1)) { // 初始化头结点

    }

    bool search(int target) {
        SkiplistNode* cur = head;
        int level = cur->next.size();
        for (int i = level - 1; i >= 0; --i) // 从上往下
        {
            while (cur->next[i] && cur->next[i]->val < target)
            {
                cur = cur->next[i];
            }
            if (cur->next[i] && cur->next[i]->val == target)
            {
                return true;
            }
        }

        return false;
    }

    void add(int num) {
        SkiplistNode* cur = head;
        int level = cur->next.size();
        vector<SkiplistNode*> pre(MAX_LEVEL, nullptr); // 记录每一层的pre节点
        for (int i = level - 1; i >= 0; --i) // 从上往下，找到应该插入的层和位置
        {
            while (cur->next[i] && cur->next[i]->val < num)
            {
                cur = cur->next[i];
            }
            pre[i] = cur;// pre为插入点的先驱节点，因为新节点的层数还不确定，所以pre需要保存每一层的先驱
        }

        // 简单起见，随机新节点的层数，最少一层
        int new_level = rand() % MAX_LEVEL + 1;
        SkiplistNode* new_node = new SkiplistNode(num, new_level);
        for (int i = new_level - 1; i >= 0; --i)// 根据pre数组把每一层的赋值
        {
            new_node->next[i] = pre[i]->next[i];
            pre[i]->next[i] = new_node;
        }        
    }

    bool erase(int num) {
        // 和add相同，要记录每一层的先驱
        SkiplistNode* cur = head;
        int level = cur->next.size();
        vector<SkiplistNode*> pre(MAX_LEVEL, nullptr); // 记录每一层的pre节点
        SkiplistNode* target = nullptr;
        for (int i = level - 1; i >= 0; --i) // 从上往下，找到应该插入的层和位置
        {
            while (cur->next[i] && cur->next[i]->val < num)
            {
                cur = cur->next[i];
            }
            if (cur->next[i] && cur->next[i]->val == num)
            {
                pre[i] = cur;
                target = cur->next[i];
            }  
        }
        if (!target)
        {
            return false;
        }

        // 删除
        for (int i = target->next.size() - 1; i >= 0; --i)
        {
            pre[i]->next[i] = target->next[i];
            target->next[i] = nullptr;
        }
        delete target;
        return true;
    }

private:
    SkiplistNode* head;
};

[snmyj]

class Skiplist {
public:
    unordered_map<int,int> hashs;
    Skiplist() {

    }

    bool search(int target) {
        if(!hashs.count(target)) return false;
        return true;
    }

    void add(int num) {
           hashs[num]++; 
    }

    bool erase(int num) {
          if(!hashs.count(num)) return false;
          else{ 
              if(hashs[num]>=1){ 
              hashs[num]--;
               if(hashs[num]==0) hashs.erase(num);
              return true;
            }
             else return false;
          }
    }

};

[harperz24]

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):
            while curr.forward[i] and curr.forward[i].val < target:
                curr = curr.forward[i]
        curr = curr.forward[0]

        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):
            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):

            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

            update[i].forward[i] = curr.forward[i]

        while self.level > 1 and self.head.forward[self.level - 1] is None:
            self.level -= 1
        return True

[FireHaoSky]

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

[Jetery]

class Node {
    int val;
    Node[] next_point;

    public Node(int val) {
        this.val = val;
    }
}

public class Skiplist {

    int MAX_LEVEL = 16;
    int curLevel;
    Node head;

    public Skiplist() {
        curLevel = 1;
        head = new Node(-1);
        head.next_point = new Node[MAX_LEVEL];
    }

    public boolean search(int target) {
        Node temp = head;
        for (int i = MAX_LEVEL - 1; i >=0; i--) {
            while (temp.next_point[i] != null && temp.next_point[i].val <= target) {
                if (temp.next_point[i].val == target) return true;
                else temp = temp.next_point[i];
            }
        }
        if (temp.next_point[0] != null && temp.next_point[0].val == target)
            return true;
        return false;
    }

    public void add(int num) {
        int level = randomLevel(0.5);
        if (level > curLevel) curLevel = level;
        Node node = new Node(num);
        node.next_point = new Node[level];
        Node[] forward = new Node[level];
        Arrays.fill(forward, head);
        Node temp = head;
        for (int i = level - 1; i >= 0; i--) {
            while (temp.next_point[i] != null && temp.next_point[i].val < num)
                temp = temp.next_point[i];
            forward[i] = temp;
        }
        for (int i = 0; i < level; i++) {
            node.next_point[i] = forward[i].next_point[i];
            forward[i].next_point[i] = node;
        }
    }

    public boolean erase(int num) {
        Node[] forward = new Node[curLevel];
        Node temp = head;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (temp.next_point[i] != null && temp.next_point[i].val < num)
                temp = temp.next_point[i];
            forward[i] = temp;
        }
        boolean res = false;
        if (temp.next_point[0] != null && temp.next_point[0].val == num) {
            res = true;
            for (int i = curLevel - 1; i >= 0; i--)
                if (forward[i].next_point[i] != null && forward[i].next_point[i].val == num)
                    forward[i].next_point[i] = forward[i].next_point[i].next_point[i];
        }
        while (curLevel > 1 && head.next_point[curLevel - 1] == null)
            curLevel -= 1;

        return res;
    }

    public int randomLevel(double p) {
        int level = 1;
        while (Math.random() < p && level < MAX_LEVEL)
            level++;
        return level;
    }
}

[SoSo1105]

class Skiplist:

def __init__(self):
    left=[Node(-1) for _ in range(16)]
    right=[Node(20001) for _ in range(16)]
    for i in range(15):
        left[i].right=right[i]
        left[i].down=left[i+1]
        right[i].down=right[i+1]
    left[-1].right=right[-1]
    self.root=left[0]

def search(self, target: int) -> bool:
    cur=self.root
    while cur:
        if target<cur.right.val:
            cur=cur.down
        elif target>cur.right.val:
            cur=cur.right
        else:
            return True
    return False    

def add(self, num: int) -> None:
    cur=self.root
    stack=[]
    while cur:
        if cur.right.val>=num:
            stack.append(cur)
            cur=cur.down
        else:
            cur=cur.right
    pre=None
    while stack:
        cur=stack.pop()
        Node=Node(num)
        node.right=cur.right
        cur.right=node
    if pre:
        node.down=pre
    pre=node
    if random.randint(0,1):
        break

def erase(self, num: int) -> bool:
    cur=self.root
    removed=False
    while cur:
        if num<cur.right.val:
            cur=cur.down
        elif num>cur.right.val:
            cur=cur.right
        else:
            cur.right=cur.right.right
            remove=True
            cur=cur.down
    return removed

class Node: def init(self,val=0,right=None,down=None): self.val=val self.right=right self.down=down

复杂度分析

• 时间复杂度：O(logN)，其中 N 为数组长度。
• 空间复杂度：O(N)

[kangliqi1]

class Solution {

public int[] rearrangeBarcodes(int[] barcodes) {

    Map<Integer, Integer> counter = new HashMap<>();
    PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> (counter.get(y) - counter.get(x)));

    for (int num : barcodes)
        counter.put(num, counter.getOrDefault(num, 0) + 1);

    for (int num : counter.keySet())
        pq.offer(num);

    int idx = 0;

    while (pq.size() > 1) {

        int first = pq.poll(), second = pq.poll();

        barcodes[idx++] = first;
        barcodes[idx++] = second;

        counter.put(first, counter.get(first) - 1);
        counter.put(second, counter.get(second) - 1);

        if (counter.get(first) > 0)
            pq.offer(first);
        if (counter.get(second) > 0)
            pq.offer(second);
    }

    if (pq.size() > 0)
        barcodes[idx++] = pq.poll();

    return barcodes;
}

}

[JasonQiu]

class Node:
    def __init__(self, val=-1, next=None, down=None):
        self.val = val
        self.next, self.down = next, down

class Skiplist:
    def __init__(self, val=-1, next=None, down=None):
        self.dummy = Node()

    def search(self, target: int) -> bool:
        node = self.dummy
        while node:
            while node.next and node.next.val < target:
                node = node.next
            if node.next and node.next.val == target:
                return True
            node = node.down
        return False

    def add(self, num: int) -> None:
        nodes, node = [], self.dummy
        while node:
            while node.next and node.next.val < num:
                node = node.next
            nodes.append(node)
            node = node.down
        add_as_index, new_down = True, None
        while nodes and add_as_index:
            node = nodes.pop()
            node.next = Node(num, node.next, new_down)
            new_down = node.next
            add_as_index = random.getrandbits(1) == 0
        if add_as_index:
            self.dummy = Node(-1, None, self.dummy)

    def erase(self, num: int) -> bool:
        node, exists = self.dummy, False
        while node:
            while node.next and node.next.val < num:
                node = node.next
            if node.next and node.next.val == num:
                node.next = node.next.next
                exists = True
            node = node.down
        return exists

Time: O(logn) Space: O(n)

[joemonkeylee]

hard题还是不行 下一期再战吧。。

const level: number = 10
class TNode {
    val: number
    ne: TNode[] = new Array<TNode>(level)
    constructor(_val: number) {
        this.val = _val
    } 
}
class Skiplist {
    he: TNode = new TNode(-1)
    find(t: number, ns: TNode[]): void {
        let cur = this.he
        for (let i = level - 1; i >= 0; i--) {
            while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i]
            ns[i] = cur
        }
    }
    search(t: number): boolean {
        let ns: TNode[] = new Array<TNode>(level)
        this.find(t, ns)
        return ns[0].ne[0] != null && ns[0].ne[0].val == t
    }
    add(t: number): void {
        let ns: TNode[] = new Array<TNode>(level)
        this.find(t, ns)
        const node = new TNode(t)
        for (let i = 0; i < level; i++) {
            node.ne[i] = ns[i].ne[i]
            ns[i].ne[i] = node
            if (Math.round(Math.random()) == 0) break
        }
    }
    erase(t: number): boolean {
        let ns: TNode[] = new Array<TNode>(level)
        this.find(t, ns)
        const node = ns[0].ne[0]
        if (node == null || node.val != t) return false
        for (let i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i]
        return true
    }
}

[Lydia61]

1206. 设计跳表

思路

参考官方解答

代码

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

复杂度分析

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[enrilwang]

class Skiplist { public: static const int level = 8;

struct Node 
{
    int val; 
    vector<Node*> next; 
    Node(int _val) : val(_val) 
    { 
        next.resize(level, NULL); 
    }
}*head;

Skiplist() 
{
    head = new Node(-1);
}

~Skiplist() 
{
    delete head; 
}

void find(int target, vector<Node*>& pre) 
{
    auto p = head;
    for (int i = level - 1; i >= 0; i -- ) 
    { 
        while (p->next[i] && p->next[i]->val < target) p = p->next[i]; 
        pre[i] = p; 
    }
}

bool search(int target) 
{
    vector<Node*> pre(level);
    find(target, pre); 

    auto p = pre[0]->next[0]; 
    return p && p->val == target;
}

void add(int num) 
{
    vector<Node*> pre(level);
    find(num, pre); 

    auto p = new Node(num); 
    for (int i = 0; i < level; i ++ ) 
    { 
        p->next[i] = pre[i]->next[i]; 
        pre[i]->next[i] = p;
        if (rand() % 2) 
            break; 
    }
}

bool erase(int num) 
{
    vector<Node*> pre(level);
    find(num, pre); 

    auto p = pre[0]->next[0];
    if (!p || p->val != num) 
        return false;

    for (int i = 0; i < level && pre[i]->next[i] == p; i ++ ) 
    {
        pre[i]->next[i] = p->next[i];
    }

    delete p;
    return true;
}

};