【Day 91 】2022-03-12 - 1206. 设计跳表

[azl397985856]

1206. 设计跳表

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

null

[yetfan]

思路 全勤，完结撒花！✿✿ヽ(°▽°)ノ✿

代码

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

[zhangzz2015]

思路

• 采用双指针的实现利用right down来实现跳表，先查找右边节点，如果找到就返回，否则进入下层节点继续查找。插入时，建立insertNodeList，然后选择一定的几率产生up节点。

  关键点

代码

• 语言支持：C++

C++ Code:

struct node
{
  node* right; 
  node* down; 
    int val; 
  node(int iVal)
  {
      val = iVal; 
      right = NULL; 
      down = NULL; 
  }

}; 
class Skiplist {
public:
    node* head; 
    Skiplist() {
        head = new node(0); 
    }

    bool search(int target) {

        bool ret = false; 
        node* current = head; 

        while(current)
        {
          //  cout << "current->right" << (current->right? current->right->val: -1) << "\n";
            while(current->right && current->right->val < target)
                current = current->right; 

            if(current->right == NULL || current->right->val >target)
            {
                current = current->down; 
            }
            else
                return true; 
        }

        return false; 
    }

    void add(int num) {
        node* current = head; 
        vector<node*> insertNodeList; 
        while(current)
        {
            while(current->right && current->right->val < num)
                current = current->right; 
            insertNodeList.push_back(current); 
            current = current->down;
        }

        node* downNode = NULL;
        bool insertUp = true; 
        while(insertNodeList.size() && insertUp)
        {
            node* prevNode = insertNodeList.back(); 
            insertNodeList.pop_back(); 

            // insert new node
            node* insertNode = new node(num); 
            insertNode->right = prevNode->right; 
            insertNode->down = downNode; 
            prevNode->right = insertNode;

            downNode = insertNode; 

            insertUp = rand()%2; // 0 or 1. 50% possible to creat up node. you may use another setting. 
        }

        if(insertUp) // when insertNodeList is empty. 
        {

            node* insertNode = new node(num); 
            insertNode->right = NULL; 
            insertNode->down = downNode;

            node* newHeadNode = new node(0); 
            newHeadNode->right = insertNode; 
            newHeadNode->down = head;

            head = newHeadNode; 
        }

        //search(num);
    }

    bool erase(int num) {

        node* current = head; 
        bool ret = false; 
        while(current)
        {
            while(current->right && current->right->val< num  )
                current= current->right; 
            if(current->right ==NULL || current->right->val>num)
            {
                current = current->down; 
            }
            else
            {
                ret = true; 
             //   delete current->right; 
                current->right = current->right->right; 
                current = current->down; 
            }
        }

        return ret; 

    }
};

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

[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
}

[dahaiyidi]

Problem

[1206. 设计跳表](https://leetcode-cn.com/problems/design-skiplist/)

++

困难

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

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

---

Note

• 跳表的实现思路很直接，就是

• 里面的重点是：

  • 实现_search函数，功能是：寻找key所经历的路径。返回路径上的前置节点。基于此可以实现add、delete
  • 随机生成一个节点的level，保证寻找的时间复杂度不会退化成n

• // http://zhangtielei.com/posts/blog-redis-skiplist.html // 参考 https://leetcode-cn.com/problems/design-skiplist/solution/javashou-xie-shi-xian-tiao-biao-by-feng-omdm0/ // https://leetcode-cn.com/problems/design-skiplist/solution/can-kao-redisshi-xian-by-bakezq/

---

Complexity

• 时间O：add: logn, delete:logn , search logn (可以近似看成一个二叉搜索树，而不能等同)
• 空间O：n

---

Python

C++

class Skiplist {
    static const int SKIPLIST_P_VAL = RAND_MAX / 2, MAX_LEVEL = 16; // RAND_MAX是rand()所能达到的最大值。
public:
    struct Node{
        int val;
        vector<Node *> next;
        Node(int val, int size = MAX_LEVEL): val(val), next(size){}
    };

    Node head;
    int maxlevel = 1; // 记录当前最高的level

    Skiplist():head(INT_MIN, MAX_LEVEL) {

    }

    bool search(int target) {
        // 在_search后就看第一层的pre的后面一个节点val是否等于target
        auto prevs = _search(target);
        return prevs[0]->next[0] && prevs[0]->next[0]->val == target;
    }

    vector<Node *> _search(int key){
        // 此函数是跳表的核心，实现的功能是，寻找key所经历的路径。返回路径上的前置节点
        Node * cur = &head;
        vector<Node *> prevs(MAX_LEVEL);
        for(int i = maxlevel - 1; i >= 0; i--){
            // 从最顶层开始
            while(cur->next[i] && cur->next[i]->val < key){
                // 一直寻找到刚好大于key的节点的前置节点
                cur = cur->next[i];
            }
            prevs[i] = cur;
        }
        return prevs;
    }

    void add(int num) {
        auto prevs = _search(num); // 在当前的跳表中， num在各级跳表中的前置节点
        int level = random_level(); // level的索引是从1开始的

        // 更新maxlevel, prevs
        if(level > maxlevel){
            // 更新超出maxlevel的prevs，前置节点都为head
            for(int i = maxlevel; i < level; i++){
                prevs[i] = &head;  
            }
            maxlevel = level;
        }

        // 创建当前节点
        Node * cur = new Node(num, level);

        // 插入在prevs节点后, 从pre->nxd到pre->cur->nx
        for(int i = level - 1; i >= 0; i--){
            cur->next[i] = prevs[i]->next[i];
            prevs[i]->next[i] = cur;
        }

    }

    bool erase(int num) {
        auto prevs = _search(num);

        // 如果num不存在跳表中
        if(!prevs[0]->next[0] || prevs[0]->next[0]->val != num){
            return false;
        }

        Node * del = prevs[0]->next[0];
        // 删除prevs后的节点
        for(int i = 0; i < maxlevel; i++){
            if(prevs[i]->next[i] == del){
                prevs[i]->next[i] = del->next[i];
            }
        }
        delete del;

        // 更新maxlevel
        while(maxlevel > 1 && !head.next[maxlevel - 1]){
            maxlevel--;
        }
        return true;

    }

    static int random_level(){
        int level = 1;
        while(rand() < SKIPLIST_P_VAL && level < MAX_LEVEL){
            level++;
        }
        return level; // 此处返回的level的索引是从1开始的
    }
};
// http://zhangtielei.com/posts/blog-redis-skiplist.html
// 参考 https://leetcode-cn.com/problems/design-skiplist/solution/javashou-xie-shi-xian-tiao-biao-by-feng-omdm0/
// https://leetcode-cn.com/problems/design-skiplist/solution/can-kao-redisshi-xian-by-bakezq/
/**
 * 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);
 */

From : https://github.com/dahaiyidi/awsome-leetcode

[LannyX]

代码

class Node{
    int val;
    Node right;
    Node down;

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

class Skiplist {
    private Node head;

    public Skiplist() {
        Node[] left = new Node[16];
        Node[] right = new Node[16];
        for(int i = 0; i < 16; i++){
            left[i] = new Node(-1);
            right[i] = new Node(20001);
        }
        for(int i = 0; i < 15; i++){
            left[i].right = right[i];
            left[i].down = left[i + 1];
            right[i].down = right[i + 1];
        }
        left[15].right = right[15];
        head = left[0];
    }

    public boolean search(int target) {
        Node cur = head;
        while(cur != null){
            if(cur.right.val > target){
                cur = cur.down;
            }else if(cur.right.val < target){
                cur = cur.right;
            }else{
                return true;
            }
        }
        return false;
    }

    public void add(int num) {
        Node cur = head;
        Deque<Node> stack = new LinkedList<>();
        while(cur != null){
            if(cur.right.val >= num){
                stack.push(cur);
                cur = cur.down;
            }else{
                cur = cur.right;
            }
        }
        Node pre = null;
        while(!stack.isEmpty()){
            cur = stack.pop();
            Node node = new Node(num);
            node.right = cur.right;
            cur.right = node;
            if(pre != null) node.down = pre;
            pre = node;

            if(Math.random() < 0.5) break;
        }
    }

    public boolean erase(int num) {
        Node cur = head;
        boolean isRemoved = false;
        while(cur != null){
            if(cur.right.val >= num){
                if(cur.right.val == num){
                    isRemoved = true;
                    cur.right = cur.right.right;
                }
                cur = cur.down;
            }else{
                cur = cur.right;
            }
        }
        return isRemoved;
    }
}

[googidaddy]

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

[Richard-LYF]

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

[Tesla-1i]

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

[liuzekuan]

Java Code:

class Skiplist {
    //跳表的节点对象
    private class Node {
        int val;

        Node right, down;

        Node(int val, Node right, Node down) {
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }
    //跳表的最大层数
    private int max;
    //最左上角的头结点
    private Node head;
    //所有头结点集合，也可以使用数组，这里为了代码简单使用List，注意所有的头结点均为虚拟节点
    private List<Node> heads;
    //随机数不解释
    private Random random;
    //构造函数初始化
    public Skiplist() {
        this.max = 64;
        this.head = new Node(0, null, null);
        this.heads = new ArrayList<Node>(this.max);
        this.heads.add(head);
        this.random = new Random();
    }
    //因为头结点为虚拟节点，所以使用do-while循环，从左到右、从上到下
    //右侧节点不为空，再分为小于目标、大于目标、等于目标三种情况处理
    public boolean search(int target) {
        Node node = head;
        do {
            if (node.right != null) {
                if (node.right.val < target) {
                    node = node.right;
                } else if (node.right.val > target) {
                    node = node.down;
                } else {
                    return true;
                }
            } else {
                node = node.down;
            }
        } while (node != null);
        return false;
    }
    //思路与search类似，先找到最下层的插入位置插入目标
    //再根据最大层数和随机概率选择是否复制最后一层
    //随机概率小于二的当前层数次方分之一才复制
    //复制是最耗时间的，但是却能提升以后操作的速度
    //所以层数越多，越要减少复制的次数
    //尝试过恒定二分之一、当前层数分之一、二的当前层数次方分之一
    //最后一种方式速度表现的效果最好
    public void add(int num) {
        Node node = head;
        do {
            if (node.right != null) {
                if (node.right.val <= num) {
                    node = node.right;
                } else if (node.down != null) {
                    node = node.down;
                } else {
                    break;
                }
            } else {
                if (node.down != null) {
                    node = node.down;
                } else {
                    break;
                }
            }
        } while (node != null);
        node.right = new Node(num, node.right, null);
        if (this.heads.size() < this.max && random.nextFloat() < 1f / Math.pow(2,this.heads.size())) {
            Node up = this.heads.get(this.heads.size() - 1);
            Node downHead = new Node(0, null, null);
            Node down = downHead;
            while (up != null) {
                up.down = down;
                if (up.right != null) {
                    down.right = new Node(up.right.val, null, null);
                }
                up = up.right;
                down = down.right;
            }
            this.heads.add(downHead);
        }
    }
    //代码基本与search相同，唯一不同是search找到第一个后即结束
    //erase要把整个表中的每一层找完才能结束
    public boolean erase(int num) {
        Node node = head;
        boolean exits = false;
        do {
            if (node.right != null) {
                if (node.right.val < num) {
                    node = node.right;
                } else if (node.right.val > num) {
                    node = node.down;
                } else {
                    node.right = node.right.right;
                    node = node.down;
                    exits = true;
                }
            } else {
                node = node.down;
            }
        } while (node != null);
        return exits;
    }
}

[hdyhdy]

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) (ans bool) {
    node := this.head
    for node != nil {
        if node.right.value > num {
            node = node.down
        } else if node.right.value < num {
            node = node.right
        } else {
            ans = true
            node.right = node.right.right
            node = node.down
        }
    }
    return
}

[1149004121]

1206. 设计跳表

思路

跳表

代码

var Skiplist = function() {
    this.head = new Node(null);
};

/** 
 * @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 if(cur.next.val === target){
            return true;
        }
    };
    return false;
};

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

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

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

 function Node(val, next, down){
     this.val = val;
     this.next = next || null;
     this.down = down || null;
 }

复杂度分析

• 时间复杂度：O(logN) 。
• 空间复杂度：O(N) 。

[declan92]

java

class Skiplist {
        /**
         * 最大层数
         */
        private static int DEFAULT_MAX_LEVEL = 32;
        /**
         * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
         */
        private static double DEFAULT_P_FACTOR = 0.25;

        Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

        int currentLevel = 1; //表示当前nodes的实际层数，它从1开始

        public Skiplist() {
        }

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

        /**
         *
         * @param num
         */
        public void add(int num) {
            int level = randomLevel();
            Node updateNode = head;
            Node newNode = new Node(num,level);
            // 计算出当前num 索引的实际层数，从该层开始添加索引
            for (int i = currentLevel-1; i>=0; i--) {
                //找到本层最近离num最近的list
                updateNode = findClosest(updateNode,i,num);
                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 (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
                for (int i = currentLevel; i < level; i++) {
                    head.next[i] = newNode;
                }
                currentLevel = level;
            }

        }

        public boolean erase(int num) {
            boolean flag = false;
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, num);
                if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                    //找到该层中该节点
                    searchNode.next[i] = searchNode.next[i].next[i];
                    flag = true;
                    continue;
                }
            }
            return flag;
        }

        /**
         * 找到level层 value 大于node 的节点
         * @param node
         * @param levelIndex
         * @param value
         * @return
         */
        private Node findClosest(Node node,int levelIndex,int value){
            while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
                node = node.next[levelIndex];
            }
            return node;
        }

        /**
         * 随机一个层数
         */
        private static int randomLevel(){
            int level = 1;
            while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
                level ++ ;
            }
            return level;
        }

        class Node{
            Integer value;
            Node[] next;

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

            @Override
            public String toString() {
                return String.valueOf(value);
            }
        }
}

时间:$O(logn)$ 空间:$O(n)$

[tian-pengfei]

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;
    }
};

[AIBotao]

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) (ans bool) { node := this.head for node != nil { if node.right.value > num { node = node.down } else if node.right.value < num { node = node.right } else { ans = true node.right = node.right.right node = node.down } } return }

[callmeerika]

思路

跳表

代码

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

/** 
 * @param {number} target
 * @return {boolean}
 */
Skiplist.prototype.search = function(target) {
    let head = this.head;
    while (head) {
        while (head.next && head.next.val < target) {
            head = head.next;
        }
        if (!head.next || head.next.val > target) {
            head = head.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 isNeedInsert = true;
    let downNode = null;
    while (isNeedInsert && stack.length) {
        let pre = stack.pop();
        pre.next = new Node(num, pre.next, downNode);
        downNode = pre.next;
        isNeedInsert = Math.random() < 0.5;
    }
    if (isNeedInsert) {
        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;
};

复杂度

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

[guangsizhongbin]

const ( maxLevel = 31 )

// 初始化随机数种子 func init() { rand.Seed(time.Now().UnixNano()) }

type Skiplist struct { CurrentLevel int Head *Node }

type Node struct { Val int Prev []Node Next []Node }

// 构造函数 func Constructor() Skiplist { head := &Node{} for i := 0; i < maxLevel; i++ { head.Next = append(head.Next, nil) } return Skiplist{CurrentLevel: 0, Head: head} }

// 生成随机数 func randomLevel() int { level := 0 for rand.Intn(2) == 1 { level++ } if level > maxLevel { level = maxLevel } return level }

// 创建一个节点 func newNode(num int, level int) Node { next := make([]Node, level + 1) prev := make([]*Node, level + 1) node := &Node{Val: num, Prev: prev, Next: next} return node }

// 查找跳表内是否有指定元素 func (l *Skiplist) Search(target int) bool { res := l.search(target) return res != nil }

func (l Skiplist) search(target int) Node { node := l.Head for i := l.CurrentLevel; i >= 0; i-- { for node.Next[i] != nil && node.Next[i].Val <= target { node = node.Next[i] } if node != l.Head && node.Val == target { return node } } return nil }

// 新增数据到跳表 func (l *Skiplist) Add(num int) { // 生成随机层数 level := randomLevel() node := newNode(num, level) // 插入元素到跳表内 updateN := l.Head // 因为数组下标从 0 开始，所以实际插入时从 CurrentLevel - 1 开始 // 而这里i如果从CurrentLevel开始，可以一下子跳过很多没必要的节点 for i := l.CurrentLevel; i >= 0; i-- { // FIXME: 这一段必须要放在if外面 // 因为越早的查询，就可以跳过越多的节点 updateN = l.findClosest(updateN, i, num) if i <= level { node.Prev[i] = updateN node.Next[i] = updateN.Next[i] updateN.Next[i] = node if node.Next[i] != nil { node.Next[i].Prev[i] = node } } } // 处理高于链表原有层数的节点 if level > l.CurrentLevel { for i := l.CurrentLevel + 1; i <= level; i++ { l.Head.Next[i] = node node.Prev[i] = l.Head } // 更新最大层级 l.CurrentLevel = level } }

// 查找最后一个小于 num 的元素 func (l Skiplist) findClosest(n Node, level int, val int) *Node { for n.Next[level] != nil && n.Next[level].Val < val { n = n.Next[level] } return n }

// 从跳表中删除元素 func (l *Skiplist) Erase(num int) bool { node := l.search(num) if node == nil { return false } for i := 0; i < len(node.Next); i++ { prev, next := node.Prev[i], node.Next[i] prev.Next[i] = next if next != nil { next.Prev[i] = prev } } return true }

[Hacker90]

跳表

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

/**

• @param {number} target
• @return {boolean} */ Skiplist.prototype.search = function(target) { let head = this.head; while (head) { while (head.next && head.next.val < target) { head = head.next; } if (!head.next || head.next.val > target) { head = head.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 isNeedInsert = true; let downNode = null; while (isNeedInsert && stack.length) { let pre = stack.pop(); pre.next = new Node(num, pre.next, downNode); downNode = pre.next; isNeedInsert = Math.random() < 0.5; } if (isNeedInsert) { 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; };

[charlestang]

思路

参见教程

代码

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

[fornobugworld]

class Skiplist { /**

• 最大层数 */ private static int DEFAULT_MAX_LEVEL = 32; /**

• 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1 */ private static double DEFAULT_P_FACTOR = 0.25;

  Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点
  
  int currentLevel = 1; //表示当前nodes的实际层数，它从1开始
  
  public Skiplist() {
  }
  
  public boolean search(int target) {
      Node searchNode = head;
      for (int i = currentLevel-1; i >=0; i--) {
          searchNode = findClosest(searchNode, i, target);
          if (searchNode.next[i]!=null && searchNode.next[i].value == target){
              return true;
          }
      }
      return false;
  }
  
  /**

• @param num */ public void add(int num) { int level = randomLevel(); Node updateNode = head; Node newNode = new Node(num,level); // 计算出当前num 索引的实际层数，从该层开始添加索引 for (int i = currentLevel-1; i>=0; i--) { //找到本层最近离num最近的list updateNode = findClosest(updateNode,i,num); 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 (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode for (int i = currentLevel; i < level; i++) { head.next[i] = newNode; } currentLevel = level; }

  }
  
  public boolean erase(int num) {
      boolean flag = false;
      Node searchNode = head;
      for (int i = currentLevel-1; i >=0; i--) {
          searchNode = findClosest(searchNode, i, num);
          if (searchNode.next[i]!=null && searchNode.next[i].value == num){
              //找到该层中该节点
              searchNode.next[i] = searchNode.next[i].next[i];
              flag = true;
              continue;
          }
      }
      return flag;
  }
  
  /**

• 找到level层 value 大于node 的节点
• @param node
• @param levelIndex
• @param value

• @return */ private Node findClosest(Node node,int levelIndex,int value){ while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){ node = node.next[levelIndex]; } return node; }

  /**

• 随机一个层数 */ private static int randomLevel(){ int level = 1; while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){ level ++ ; } return level; }

  class Node{
      Integer value;
      Node[] next;
  
      public Node(Integer value,int size) {
          this.value = value;
          this.next = new Node[size];
      }
  
      @Override
      public String toString() {
          return String.valueOf(value);
      }
  }

  }

[machuangmr]

代码

class Skiplist {

   /* 最大层数
         */
        private static int DEFAULT_MAX_LEVEL = 32;
        /**
         * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
         */
        private static double DEFAULT_P_FACTOR = 0.25;

        Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

        int currentLevel = 1; //表示当前nodes的实际层数，它从1开始

    public Skiplist() {

    }

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

    }

    public void add(int num) {
         int level = randomLevel();
            Node updateNode = head;
            Node newNode = new Node(num,level);
            // 计算出当前num 索引的实际层数，从该层开始添加索引
            for (int i = currentLevel-1; i>=0; i--) {
                //找到本层最近离num最近的list
                updateNode = findClosest(updateNode,i,num);
                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 (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
                for (int i = currentLevel; i < level; i++) {
                    head.next[i] = newNode;
                }
                currentLevel = level;
            }

    }

    public boolean erase(int num) {
        boolean flag = false;
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, num);
                if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                    //找到该层中该节点
                    searchNode.next[i] = searchNode.next[i].next[i];
                    flag = true;
                    continue;
                }
            }
            return flag;

    }
     private Node findClosest(Node node,int levelIndex,int value){
            while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
                node = node.next[levelIndex];
            }
            return node;
        }
      private static int randomLevel(){
            int level = 1;
            while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
                level ++ ;
            }
            return level;
        }
 class Node{
            Integer value;
            Node[] next;

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

            @Override
            public String toString() {
                return String.valueOf(value);
            }
        }

}

[zzzpppy]

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++;//跳表层数加一

            }
        }
    }
}

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

[taojin1992]

class Skiplist {
    Node head;

    class Node {
        int val;
        Node next;
        Node down;

        Node(int val, Node next, Node down) {
            this.val = val;
            this.next = next;
            this.next = down;
        }
    }

    public Skiplist() {
        head = new Node(0, null, null);
    }

    public boolean search(int target) {
        Node cur = head;
        while (cur != null) {
    // go rightmost
    while (cur.next != null && cur.next.val < target) {
        cur = cur.next;
    }
    // cur is the rightmost node that is less than target
            if (cur.next != null && cur.next.val == target) {
        return true;
    }
            cur = cur.down;
/*
            else if (cur.next == null || cur.next.val > target) {
        cur = cur.down;
}   
*/
        }
        return false;
    }

    public void add(int num) {
    // store all the nodes from level 4 to level 1 that can potentially have this new node as the next into the stack
    Stack<Node> stack = new Stack<>();
    // do search and push into stack
    Node cur = head;
        while (cur != null) {
        // go rightmost
        while (cur.next != null && cur.next.val < num) {
            cur = cur.next;
        }
        // cur is the rightmost node that is less than num
                stack.push(cur);
                cur = cur.down;
    }
            // prob = 1 for stack.pop()
    Node curLevel = stack.pop();
    // Node curLevel_next = curLevel .next;
    Node nodeToInsert= new Node(num, curLevel.next, null);
    curLevel.next = nodeToInsert;
    // nodeToInsert.next =  curLevel_next; redundant

    while (!stack.isEmpty()) {
        Random rand = new Random(); 
        double prob = rand.nextDouble();
        Node pre = nodeToInsert;
        if (prob >= 0.5) {
            curLevel = stack.pop();
            nodeToInsert= new Node(num, curLevel.next, pre); // reset the down pointer
            curLevel.next = nodeToInsert;
            pre = nodeToInsert;
        } else {
            return;
        }
    } 
    }

    //  If there exists multiple num values, removing any one of them is fine.
// remove one from the same level and remove the same value for all the levels
    public boolean erase(int num) {
            Node cur = head;
    boolean flag = false;
    while (cur != null) {
        while  (cur.next != null && cur.next.val < num) {
            cur = cur.next;
        } 
        if (cur.next != null && cur.next.val == num) {
            cur.next = cur.next.next;
flag = true;
        } 
        cur = cur.down;
    }
    return flag;
    }
}

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

[falconruo]

思路:

复杂度分析:

• 时间复杂度: 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; // random layer

        while (rlayer <= layer && (rand() & 1) == 0) ++rlayer; // need to add a new layer for the new element
        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);
 */

[honeymeng-hub]

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