【Day 91 】2021-12-09 - 1206. 设计跳表

[azl397985856]

1206. 设计跳表

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

null

[yanglr]

思路:

需要实现以下 3 个函数:

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

代码:

实现语言: C++
​

struct Node {
    Node *right, *down;
    int val;
    Node(Node* right, Node* down, int val): right(right), down(down), val(val) {}
};

class Skiplist {
    Node* head;
    vector<Node*> insertPoints;    
    
public:
    Skiplist() { 
        head = new Node(nullptr, nullptr, 0); 
    }    
    bool search(int target) {
        Node* p = head;
        while (p)
        {
            while (p->right && p->right->val < target) /* 找当前层的1个适合的区间: 如果p->right变成NULL或target <= p->right结点的值时说明找到合适位置了, 否则继续右移 */
                p = p->right;
            if (!p->right || p->right->val > target) // 没找到, 就继续到下1层去找
                p = p->down;
            else
                return true;
        }
        return false;
    }
    void add(int num)
    {
        insertPoints.clear();
        Node* p = head;
        while (p)
        {
            while (p->right && p->right->val < num)
                p = p->right;
            insertPoints.push_back(p);
            p = p->down;
        }

        Node* downNode = nullptr;
        bool insertUp = true;
        while (insertUp && insertPoints.size())
        {
            Node* ins = insertPoints.back();
            insertPoints.pop_back();

            ins->right = new Node(ins->right, downNode, num);
            downNode = ins->right;

            insertUp = (rand() & 1) == 0; // 50% 的可能性
        }
        if (insertUp) // 创建一个新的layer
        {
            head = new Node(new Node(nullptr, downNode, num), head, 0);
        }
    }
    bool erase(int num)
    {
        Node* p = head;
        bool seen = false;  // 跳表中是否存在要删的值
        while (p)
        {
            while (p->right && p->right->val < num)
                p = p->right;
            if (!p->right || p->right->val > num) // 没找到要删的值, 就继续到下1层去找
                p = p->down;
            else  /* 找到了要删的值, 就删除这个结点 */
            {
                seen = true;
                p->right = p->right->right;
                p = p->down;
            }
        }
        return seen;
    }
};

复杂度分析:

跳表查询、插入、删除的复杂度均为:

• 时间复杂度: O(log n)
• 空间复杂度: O(n)

跳表的时间复杂度和空间复杂度不是很好分析。由于时间复杂度 = 索引的高度 * 平均每层索引遍历元素的个数，而高度大概为 log n，并且每层遍历的元素是常数，因此时间复杂度为 log n。

空间复杂度就等同于索引节点的个数，以每两个节点建立一个索引为例，大概是 n/2 + n/4 + n/8 + … + 8 + 4 + 2 ，因此空间复杂度是 O(n)。

[ysy0707]

复制题解学习
class Skiplist {
final int HEAD_VALUE = -1;
final Node HEAD = new Node(HEAD_VALUE);

Node head ;//最左上角的头节点
int levels;//当前层级，即head节点所在的最高层数
int length;//跳表长度，即原链表的节点个数

//定义节点类
class Node{
    int val;
    Node right,down;

    Node(int val){
        this(val,null,null);
    }
    //声明节点的值value以及向右和向左的两个指针right、down
    Node(int val,Node right,Node down){
        this.val = val;
        this.right = right;
        this.down = down;
    }
}

//初始化跳表
public Skiplist() {
    head = HEAD;
    levels = 1;
    length = 1;
}

/**
 * 查找方法：从head开始，从左往右，从上往下查找
 * 1.若节点值小于目标值，则往右查找
 * 2.节点值等于目标值，则返回true
 * 3.节点值大于目标值,则向下一层级查找
 * @param target
 * @return
 */
public boolean search(int target) {
    Node node = head;
    while (node != null){
        //1.在同一层级上，从左往右查找知道链表的结尾
        while (node.right != null && node.right.val < target){
            node = node.right;
        }
        //2.若找到符合条件的节点,即该节点的值与target相等,则返回true
        if (node.right != null && node.right.val == target){
            return true;
        }
        //3.若node.right的值大于目标target,则向下一层
        node = node.down;
    }
    //若在最后一层也未找到符合条件的节点，则返回false
    return false;
}

/**
 * 删除方法：逐层遍历，并删除每一层符合条件的节点
 * 1.获取指定数据节点的前一个节点
 * 2.将指定节点与当前层链表断开
 * 3.下移，重复1 2操作
 * @param num
 * @return
 */
public boolean erase(int num) {
    Node node = head;
    boolean exist = false;
    while (node != null){
        //1.获取指定数据节点的前一个节点
        while (node.right != null && node.right.val < num){
            node = node.right;
        }
        //2.若该节点为目标节点，则将其与当前层链表断开
        Node right = node.right;//需要断开的节点
        if (right != null && right.val == num){
            //断开操作
            node.right = right.right;
            right.right = null;
            exist = true;
        }
        //3.下移，重复之前操作
        node = node.down;
    }
    return exist;
}

/**
 * 插入方法：将节点插入到原链表中正确的排序位置
 * 1.定位插入位置;在原链表中>=num的最小节点前
 * 2.插入节点
 * 3.根据抛硬币决定是否建立索引
 * @param num
 */
public void add(int num) {
    Node node = head;
    //使用数组记录，每一层可能生成索引位置的节点
    Node[] nodes = new Node[levels];
    int i = 0;//用于操作上述数组
    //1.定位插入位置;在原链表中>=num的最小节点前
    while (node != null){
        while (node.right != null && node.right.val < num){
            node = node.right;
        }
        //右侧可能为null，或大于目标数值，或等于目标数值
        nodes[i++] = node;
        //继续查找下一层的位置
        node = node.down;
    }

    //2.插入新节点
    //取出nodes中的最后一个元素。即原链表中<num的最大的一个节点
    node = nodes[--i];//在操作1中最后i多加了1越界，所以需要减1后使用
    //进行插入操作
    Node newNode = new Node(num,node.right,null);
    node.right = newNode;
    length++;//原链表的长度加一

    //3.根据抛硬币决定是否建立索引
    //自定义方法
    addIndicesByCoinFlip(newNode,nodes,i);//i的值代表索引层数，不包括原链表
}

/**
 * 抛硬币决定是否给新节点建立索引
 * 索引层级可能超过现有跳表的层数，再抛一次硬币决定是否生成更高的索引
 * 1.抛硬币，决定是否给在现有跳表层级建立索引
 * 2.抛硬币，决定是否建立超过跳表层数的索引层
 * @param target
 * @param nodes
 * @param indices
 */
private void addIndicesByCoinFlip(Node target,Node[] nodes,int indices){
    Node downNode = target;
    Random random = new Random();
    int coins = random.nextInt(2);//0 or 1
    while(coins == 1 && levels < (length >> 6)){
        if (indices > 0){
            Node prev = nodes[--indices];//首先时数组中的倒数第二个元素
            //建立索引
            Node newNode = new Node(target.val,prev.right,downNode);
            prev.right = newNode;
            //更新downNode
            downNode = newNode;
            coins = random.nextInt(2);
        }else {//新建一个索引层级
            //新建索引节点和head节点
            Node newNode = new Node(target.val,null,downNode);
            Node newhead = new Node(HEAD_VALUE,newNode,head);
            head = newhead;//head指针上移
            levels++;//跳表层数加一

        }
    }
}

}

[biancaone]

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

class Skiplist(object):
    def __init__(self):
        self.head = Node(-1, 16) 
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                future = cur.levels[level]
                if future and future.val < num:
                    cur = future
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self._iter(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
        node = Node(num, nodelvls)
        
        for cur, level in self._iter(num):
            if level < nodelvls:
                future = cur.levels[level]
                cur.levels[level] = node
                node.levels[level] = future

    def erase(self, num):
        ans = False
        for cur, level in self._iter(num):
            future = cur.levels[level]
            if future and future.val == num:
                ans = True
                cur.levels[level] = future.levels[level]
        return ans

[pophy]

思路

• 跳表设计
• 多层LinkedList，每层排序
• 检索跳表类似于快进 比如2x/4x/8x/16x, 从高倍速找出第一个小于target的node，然后跳下一层
• 添加node的时候， 从上到下找出小于target的node，放入Stack, 再从下往上概率添加
  • 概率为 0.5^(d) d = 层高, d == 0 时 100%添加
• 删除node， 从上往下查询 如果找到node.right == target, 则node.right = node.right.right, 并下跳一层

Java Code

class Skiplist {    
    ListNode head;
    Random random = new Random();
    public Skiplist() {
        head = new ListNode(-1, null, null);
    }
    public boolean search(int target) {
        ListNode p = head;
        while (p != null) {
            while (p.right != null && p.right.val < target) {
                p = p.right;
            }
            if (p.right != null && p.right.val == target) {
                return true;
            }
            p = p.down;
        }
        return false;
    }
    public void add(int num) {
        ListNode p = head;
        Deque<ListNode> stack = new ArrayDeque();
        while (p != null) {
            while (p.right != null && p.right.val < num) {
                p = p.right;
            }
            stack.push(p);
            p = p.down;
        }
        boolean insert = true;
        ListNode down = null;
        while (insert && !stack.isEmpty()) {
            p = stack.pop();
            p.right = new ListNode(num, p.right, down);
            insert = insert && random.nextInt(2) == 0;
            down = p.right;
        }
        if (insert) {
            this.head = new ListNode(-1, null, head);
        }

    }
    public boolean erase(int num) {
        ListNode p = head;
        boolean found = false;
        while (p != null) {
            while (p.right != null && p.right.val < num) {
                p = p.right;
            }
            if (p.right != null && p.right.val == num) {
                p.right = p.right.right;
                found = true;
            }
            p = p.down;
        }
        return found;
    }     
    private static class ListNode {
        int val;
        ListNode right;
        ListNode down;

        public ListNode(int val, ListNode right, ListNode down) {
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }    
}

时间&空间

• 时间 O(log(n))
• 空间 O(n)

[wenjialu]

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

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.head = left[0]
    
def search(self, target: int) -> bool:
    cur = self.head
    while cur:
        if cur.right.val > target:
            cur = cur.down
        elif cur.right.val < target:
            cur = cur.right
        else:
            return True
    return False
       
def add(self, num: int) -> None:
    cur = self.head
    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.head
    is_removed = False
    while cur:
        if cur.right.val >= num:
            if cur.right.val == num:
                is_removed = True
                cur.right = cur.right.right
            cur = cur.down
        else:
            cur = cur.right
    return is_removed

[ginnydyy]

Problem

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

Note

• skiplist
• Java solution reference: https://leetcode-cn.com/problems/design-skiplist/solution/javashou-xie-shi-xian-tiao-biao-by-feng-omdm0/

Solution

class Skiplist {
    private static final double P = 0.25d;
    private static final int MAX_LEVEL = 32;
    private Node head = new Node(null, MAX_LEVEL);
    private int curLevel = 1;
    
    public Skiplist() {
        
    }
    
    public boolean search(int target) {
        // search from head from upper level 
        Node searchNode = head;
        for(int i = curLevel - 1; i >= 0; i--){
            searchNode = findClosest(searchNode, i, target);
            if(searchNode.next[i] != null && searchNode.next[i].val == target){
                return true;
            }
        }
        return false;
    }
    
    public void add(int num) {
        int level = randomLevel();
        Node newNode = new Node(num, level);
        Node updateNode = head; // start from head, and find the closest node to the new node
        
        // process all the existing levels
        for(int i = curLevel - 1; i >= 0; i--){
            updateNode = findClosest(updateNode, i, num);// find and update the closest node for each level
            if(i < level){ // add newNode to the current level only if i < level
                if(updateNode.next[i] == null){
                    updateNode.next[i] = newNode;
                }else{
                    Node temp = updateNode.next[i];
                    updateNode.next[i] = newNode;
                    newNode.next[i] = temp;
                }
            }
        }
        
        // if the random level is > curLevel, put the new node in the new levels, and increase the curLevel
        if(level > curLevel){ // 
            for(int i = curLevel; i < level; i++){
                head.next[i] = newNode;
            }
            curLevel = level;
        }
    }
    
    public boolean erase(int num) {
        // search from head from upper level 
        Node searchNode = head;
        boolean flag = false;
        for(int i = curLevel - 1; i >= 0; i--){
            searchNode = findClosest(searchNode, i, num);
            if(searchNode.next[i] != null && searchNode.next[i].val == num){
                searchNode.next[i] = searchNode.next[i].next[i];
                flag = true; // shouldn't return immediately, need to erase the node at every level
            }
        }        
        return flag;
    }
    
    // start from the given node, find the closest node at the given level, so that the given val is > the closest node's val and the given val is <= node's next val
    private Node findClosest(Node node, int levelIndex, int val){
        while(levelIndex < node.next.length && node.next[levelIndex] != null && val > node.next[levelIndex].val){
            node = node.next[levelIndex];
        }
        return node;
    }
    
    // get a random level
    private int randomLevel(){
        int level = 1;
        while(Math.random() < P && level < MAX_LEVEL){
            level++;
        }
        return level;
    }
}

class Node{
    Integer val;
    Node[] next;
    public Node(Integer val, int size){
        this.val = val;
        this.next = new Node[size];
    }
}

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

Complexity

• T: The add operation, search operation and erase operation are O(logn). n is the size of the list at the bottom level (the number of nodes at the bottom level).
• S: O(n). Each level has max n nodes.

[yunomin]

class Solution:
    def rearrangeBarcodes(self, barcodes: List[int]) -> List[int]:
        
        m = {}
        for i in barcodes:
            if i not in m:
                m[i] = 1
            else:
                m[i] += 1
        index = [i for i in range(0, len(barcodes), 2)] + [i for i in range(1, len(barcodes), 2)]
        res = [-1 for _ in barcodes]
        i = 0
        while len(m) > 0:
            k = max(m, key=m.get)
            for j in range(m[k]):
                res[index[i]] = k
                i += 1
            del m[k]
        return res
        

[yan0327]

const (
    maxLevel = 16
    maxRand = 65535.0
)
func randLevel() int{
    return maxLevel - int(math.Log2(1.0+maxRand*rand.Float64()))
}
type skipNode struct{
    value int
    right *skipNode
    down *skipNode
}
type Skiplist struct {
    head *skipNode
}


func Constructor() Skiplist {
    left := make([]*skipNode,maxLevel)
    right := make([]*skipNode,maxLevel)
    for i:=0;i<maxLevel;i++{
        left[i] = &skipNode{-1,nil,nil}
        right[i] = &skipNode{20001,nil,nil}
    }
    for i:= maxLevel-2;i>=0;i--{
        left[i].right = right[i]
        left[i].down = left[i+1]
        right[i].down = right[i+1]
    }
    left[maxLevel-1].right = right[maxLevel-1]
    return Skiplist{left[0]}
}


func (this *Skiplist) Search(target int) bool {
    node := this.head
    for node != nil{
        if node.right.value > target{
            node = node.down
        }else if node.right.value < target{
            node = node.right
        }else{
            return true
        }
    }
    return false
}


func (this *Skiplist) Add(num int)  {
    prev := make([]*skipNode,maxLevel)
    i := 0
    node := this.head
    for node != nil{
        if node.right.value >= num{
            prev[i] = node
            i++
            node = node.down
        }else{
            node = node.right
        }
    }
    n := randLevel()
    arr := make([]*skipNode,n)
    t := &skipNode{-1,nil,nil}
    for i,a := range arr{
        p := prev[maxLevel-n+i]
        a = &skipNode{num,p.right,nil}
        p.right = a
        t.down = a
        t = a
    }
}


func (this *Skiplist) Erase(num int) bool {
    node := this.head
    out := false
    for node != nil{
        if node.right.value > num{
            node = node.down
        }else if node.right.value < num{
            node = node.right
        }else{
            out = true
            node.right = node.right.right
            node = node.down
        }
    }
    return out
}


/**
 * Your Skiplist object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Search(target);
 * obj.Add(num);
 * param_3 := obj.Erase(num);
 */

[falconruo]

思路:
跳跃列表(Skiplist)

1. 用一个结构体定义跳跃节点skipNode：val为值, 节点指针right, down分别指向同一层的链表, 不同层的同一个节点

复杂度分析:

• 时间复杂度: O(logN), N为总的节点数, add/erase/search
• 空间复杂度: O(N)

代码(C++):

struct SkipNode {
    int val;
    SkipNode *right, *down;
    SkipNode(int v, SkipNode* r, SkipNode* d) : val(v), right(r), down(d) {};
};

class Skiplist {
public:
    Skiplist() {
        head = nullptr;
        layer = 0;
    }
    
    bool search(int target) {
        SkipNode* cur = head;

        while (cur) {
            while (cur->right && cur->right->val < target)
                cur = cur->right;
            if (cur->right && cur->right->val == target) return true;
            cur = cur->down;
        }
        return false;
    }
    
    void add(int num) {
        int rlayer = 1;
        while (rlayer <= layer && (rand() & 1) == 0) ++rlayer;
        if (rlayer > layer) {
            layer = rlayer;
            head = new SkipNode(num, nullptr, head);
        }

        SkipNode *cur = head, *last = nullptr;
        for (int l = layer; l >= 1; --l) {
            while (cur->right && cur->right->val < num) cur = cur->right;
            if (l <= rlayer) {
                cur->right = new SkipNode(num, cur->right, nullptr);
                if (last)
                    last->down = cur->right;
                last = cur->right;
            }
            cur = cur->down;
        }
    }
    
    bool erase(int num) {
        SkipNode *cur = head;
        bool seen = false;

        for (int l = layer; l >= 1; --l) {
            while (cur->right && cur->right->val < num) cur = cur->right;
            if (cur->right && cur->right->val == num) {
                seen = true;

                SkipNode* tmp = cur->right;
                cur->right = tmp->right;
                delete(tmp);
            }
            cur = cur->down;
        }

        return seen;
    }
private:
    SkipNode *head;
    int layer;
};

/**
 * 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);
 */

[tongxw]

思路

大致了解一下实现方式

代码

class Skiplist {
    private int MAX_LEVEL = 30;
    private Node head;
    private int curMaxLevel = 1;

    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
        curMaxLevel = 1;
    }
    
    public boolean search(int target) {
        for (int i=curMaxLevel-1; i>=0; i--) {
            Node node = findClosest(head, i, target);
            if (node.next[i] != null && node.next[i].value == target) {
                return true;
            }
        }

        return false;
    }
    
    public void add(int num) {
        int level = randomLevel();
        Node newNode = new Node(num, level);
        for (int i=curMaxLevel-1; i>=0; i--) {
            Node node = findClosest(head, i, num);
            if (i < level) {
                Node nextNode = node.next[i];
                node.next[i] = newNode;
                newNode.next[i] = nextNode;
            }
        }

        if (level > curMaxLevel) {
            for (int i=curMaxLevel; i<level; i++) {
                head.next[i] = newNode;
            }

            curMaxLevel = level;
        }
    }
    
    public boolean erase(int num) {
        boolean found = false;
        for (int i=curMaxLevel-1; i>=0; i--) {
            Node node = findClosest(head, i, num);
            if (node.next[i] != null && node.next[i].value == num) {
                node.next[i] = node.next[i].next[i];
                found = true;
            }
        }

        return found;

        
    }
    
    private Node findClosest(Node node, int levelIndex, int target) {
        while ((node.next[levelIndex] != null && node.next[levelIndex].value < target)) {
            node = node.next[levelIndex];
        }
        
        return node;
    }

    private int randomLevel() {
        double DEFAULT_P_FACTOR = 0.25;
        int level = 1;
        while(Math.random() < DEFAULT_P_FACTOR && level < MAX_LEVEL) {
            level++;
        }

        return level;
        // return new Random().nextInt(MAX_LEVEL + 1);
    }

    class Node {
        int value;
        Node[] next;

        public Node(int value, int size) {
            this.value = value;
            this.next = new Node[size];
        }
    }
}

[yingliucreates]

link:

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

代码 Javascript

const Node = function (val = -1, right = null, down = null) {
    this.val = val;
    this.right = right;
    this.down = down;
}

const Skiplist = function() {
    this.head = new Node() // dummy head
};

/** 
 * @param {number} target
 * @return {boolean}
 */
Skiplist.prototype.search = function(target) {
    var node = this.head;
    while (node) {
        while (node.right && node.right.val < target) {
            node = node.right;
        }
        if (node.right && node.right.val === target) {
            return true;
        }
        node = node.down;
    }
    return false;
};

/** 
 * @param {number} num
 * @return {void}
 */
Skiplist.prototype.add = function(num) {
    var pathlist = [];
    var node = this.head;
    while (node) {
        while (node.right && node.right.val < num) {
            node = node.right;
        }
        pathlist.push(node);
        node = node.down;
    }
    var insertUp = true;
    var downNode = null;
    while (insertUp && pathlist.length !== 0) {
        var insertNode = pathlist.pop();
        insertNode.right = new Node(num, insertNode.right, downNode);
        downNode = insertNode.right;
        insertUp = (Math.random() * 10 & 1) === 0;
    }
    if (insertUp) {
        this.head = new Node(-1, null, this.head);
    }  
};

/** 
 * @param {number} num
 * @return {boolean}
 */
Skiplist.prototype.erase = function(num) {
    var node = this.head;
    var found = false;
    while (node) {
        while (node.right && node.right.val < num) {
            node = node.right;
        }
        if (!node.right || node.right.val > num) {
            node = node.down;
        } else {
            found = true;
            node.right = node.right.right;
            node = node.down;
        }
        
    }
    return found;    
};

[zszs97]

开始刷题

题目简介

【Day 91 】2021-12-09 - 1206. 设计跳表

题目思路

• 跳表

题目代码

代码块

class Skiplist {
private:
    SkipListNode *head, *tail;
    int level, length;
public:
	static constexpr int MAXL = 32;
    static constexpr int P = 4;
    static constexpr int S = 0xFFFF;
    static constexpr int PS = S / 4;

    Skiplist() {
        level = length = 0;
        tail = new SkipListNode(INT_MAX, 0);
        head = new SkipListNode(INT_MAX);
        for (int i = 0; i < MAXL; ++i) { 
        	head->level[i] = tail;
        }
    }

    SkipListNode* find(int val) {
        SkipListNode *p = head;
        for (int i = level - 1; i >= 0; --i) {
            while (p->level[i] && p->level[i]->val < val) {
                p = p->level[i];
            }
        }
        p = p->level[0];
        return p;
    }
    
    bool search(int target) {
        SkipListNode *p = find(target);
        return p->val == target;
    }
    
    void add(int val) {
        vector<SkipListNode *> update(MAXL);
        SkipListNode *p = head;
        for (int i = level - 1; i >= 0; --i) {
            while (p->level[i] && p->level[i]->val < val) {
                p = p->level[i];
            }
            update[i] = p;
        }
        int lv = randomLevel();
        if (lv > level) {
            lv = ++level;
            update[lv - 1] = head; 
        }
        SkipListNode *newNode = new SkipListNode(val, lv);
        for (int i = lv - 1; i >= 0; --i) {
            p = update[i];
            newNode->level[i] = p->level[i];
            p->level[i] = newNode;
        }
        ++length;
    }
    
    bool erase(int val) {
        vector<SkipListNode *> update(MAXL + 1);
        SkipListNode *p = head;
        for (int i = level - 1; i >= 0; --i) {
            while (p->level[i] && p->level[i]->val < val) {
                p = p->level[i];
            }
            update[i] = p;
        }
        p = p->level[0];
        if (p->val != val) return false;
        for (int i = 0; i < level; ++i) {
            if (update[i]->level[i] != p) {
                break;
            }
            update[i]->level[i] = p->level[i];
        }
        while (level > 0 && head->level[level - 1] == tail) --level;
        --length;
        return true;
    }

    int randomLevel() {
        int lv = 1;
        while (lv < MAXL && (rand() & S) < PS) ++lv;
        return lv;
    }
};

复杂度

• 空间复杂度 O(n)
• 时间复杂度 O(logn)

[ZacheryCao]

Idea

Refer to Solutions in Leet Code

Code:

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

class Skiplist(object):
    def __init__(self):
        self.head = Node(-1, 16) 
    
    def _iter(self, num):
        cur = self.head
        for level in range(15, -1, -1):
            while True:
                future = cur.levels[level]
                if future and future.val < num:
                    cur = future
                else:
                    break
            yield cur, level

    def search(self, target):
        for prev, level in self._iter(target):
            pass
        cur = prev.levels[0]
        return cur and cur.val == target

    def add(self, num):
        nodelvls = min(16, 1 + int(math.log2(1.0 / random.random())))
        node = Node(num, nodelvls)
        
        for cur, level in self._iter(num):
            if level < nodelvls:
                future = cur.levels[level]
                cur.levels[level] = node
                node.levels[level] = future

    def erase(self, num):
        ans = False
        for cur, level in self._iter(num):
            future = cur.levels[level]
            if future and future.val == num:
                ans = True
                cur.levels[level] = future.levels[level]
        return ans