【Day 91 】2023-01-30 - 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操作。

[tiandao043]

以二分之一概率建立索引

struct Node{
    int val;
    Node *right,*down;
    Node(int v, Node* r,Node* d):val(v), right(r),down(d) {}
};
class Skiplist {
public:
    int level=0;
    Node* head=nullptr;
    Skiplist() {}

    bool search(int target) {
        Node *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 rlevel=1;
        while(rlevel<=level && (rand() & 1)==0) ++rlevel;
        if(rlevel>level){
            level=rlevel;
            head=new Node(num,nullptr,head);
        }
        Node *cur=head,*last=nullptr;
        for(int l=level;l>=1;--l){
            while(cur->right && cur->right->val <num)cur=cur->right;
            if(l<=rlevel){
                cur->right=new Node(num,cur->right,nullptr);
                if(last){
                    last->down=cur->right;
                }
                last=cur->right;
            }
            cur=cur->down;
        }
    }

    bool erase(int num) {
        Node *cur=head;
        bool seen=false;
        for(int i=level;i>=1;--i){
            while(cur->right && cur->right->val < num)cur=cur->right;
            if(cur->right && cur->right->val == num){
                seen=true;
                Node* tmp=cur->right;
                cur->right=cur->right->right;
                delete tmp;
            }
            cur=cur->down;
        }
        return seen; 
    }
};

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

[RestlessBreeze]

code

constexpr int MAX_LEVEL = 32;
constexpr double P_FACTOR = 0.25;

struct SkiplistNode {
    int val;
    vector<SkiplistNode *> forward;
    SkiplistNode(int _val, int _maxLevel = MAX_LEVEL) : val(_val), forward(_maxLevel, nullptr) {

    }
};

class Skiplist {
private:
    SkiplistNode * head;
    int level;
    mt19937 gen{random_device{}()};
    uniform_real_distribution<double> dis;

public:
    Skiplist(): head(new SkiplistNode(-1)), level(0), dis(0, 1) {

    }

    bool search(int target) {
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < target) {
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        if (curr && curr->val == target) {
            return true;
        } 
        return false;
    }

    void add(int num) {
        vector<SkiplistNode *> update(MAX_LEVEL, head);
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        int lv = randomLevel();
        level = max(level, lv);
        SkiplistNode *newNode = new SkiplistNode(num, lv);
        for (int i = 0; i < lv; i++) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
    }

    bool erase(int num) {
        vector<SkiplistNode *> update(MAX_LEVEL, nullptr);
        SkiplistNode *curr = this->head;
        for (int i = level - 1; i >= 0; i--) {
            while (curr->forward[i] && curr->forward[i]->val < num) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        curr = curr->forward[0];
        if (!curr || curr->val != num) {
            return false;
        }
        for (int i = 0; i < level; i++) {
            if (update[i]->forward[i] != curr) {
                break;
            }
            update[i]->forward[i] = curr->forward[i];
        }
        delete curr;
        while (level > 1 && head->forward[level - 1] == nullptr) {
            level--;
        }
        return true;
    }

    int randomLevel() {
        int lv = 1;
        while (dis(gen) < P_FACTOR && lv < MAX_LEVEL) {
            lv++;
        }
        return lv;
    }
};

[paopaohua]

最后一天

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

}

[klspta]

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

[Elsa-zhang]

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

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.right
            elif target < cur.right.val:
                cur = cur.down
            else:
                return True
        return False

    def add(self, num: int) -> None:
        cur = self.root
        stack = []
        while cur:
            if num <= cur.right.val:
                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
        flag = False
        while cur:
            if num > cur.right.val:
                cur = cur.right
            elif num < cur.right.val:
                cur = cur.down
            else:
                cur.right = cur.right.right
                cur = cur.down
                flag = True
        return flag

[snmyj]

class Skiplist() {
  val avgJump = 5
  var capacity: Int = avgJump
  var count = 0

  class Node(val value: Int, val down: Node, var right: Node)

  private var head = new Node(-1, null, null)

  def search(target: Int): Boolean = {
    if (count == 0) false
    else {
      val preRight = findPres(target).last.right
      preRight != null && preRight.value == target
    }
  }

  private def findPres(target: Int) = {
    val node = findPre(head, target)
    Stream.iterate(node)(up => findPre(up.down, target)) takeWhile (_ != null)
  }

  private def findPre(from: Node, target: Int): Node = {
    Iterator.iterate(from)(_.right).takeWhile(_ != null)
      .find(n => n.right == null || n.right.value >= target).orNull
  }

  def add(num: Int): Unit = {
    findPres(num).reverse
      .zip(0.0 #:: Stream.continually(math.random))
      .takeWhile(_._2 < 1.0 / avgJump)
      .map(_._1)
      .scanLeft(null: Node)((downNode: Node, pre: Node) => {
        pre.right = new Node(num, downNode, pre.right)
        pre.right
      }).force
    count += 1
    if (count > capacity) {
      head = new Node(-1, head, null)
      Stream.iterate(head.down.right)(_.right).takeWhile(_ != null)
        .filter(_ => math.random < 1.0 / avgJump)
        .scanLeft(head)((pre: Node, cur: Node) => {
          pre.right = new Node(cur.value, cur, null)
          pre.right
        }).force
      capacity *= avgJump
    }
  }

}

[bookyue]

code

class Skiplist {
    private static final int MAX_LEVEL = 32;
    private static final double SKIPLIST_P = 0.25;
    private final Node head;
    private int curLevel;

    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
        curLevel = 0;
    }

    private void find(int target, Node[] update) {
        var cur = head;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < target)
                cur = cur.next[i];

            update[i] = cur;
        }
    }

    public boolean search(int target) {
        var cur = head;
        for (int i = curLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < target)
                cur = cur.next[i];
        }

        cur = cur.next[0];
        return cur != null && cur.val == target;
    }

    public void add(int num) {
        Node[] update = new Node[MAX_LEVEL];
        Arrays.fill(update, head);
        find(num, update);

        int randomLevel = randomLevel(); // Integer.numberOfTrailingZeros(RANDOM.nextInt()) + 1; MAX_LEVEL = 33
        curLevel = Math.max(curLevel, randomLevel);
        Node newNode = new Node(num, randomLevel);

        for (int i = 0; i < randomLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }

    public boolean erase(int num) {
        Node[] update = new Node[MAX_LEVEL];
        find(num, update);

        var cur = update[0].next[0];
        if (cur == null || cur.val != num) return false;
        for (int i = 0; i < curLevel && update[i].next[i] == cur; i++)
            update[i].next[i] = cur.next[i];

        while (curLevel > 1 && head.next[curLevel - 1] == null)
            curLevel--;

        return true;
    }

    private int randomLevel() {
        int level = 1;
        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
            level++;

        return level;
    }

    private static class Node {
        int val;
        Node[] next;

        Node(int val, int level) {
            this.val = val;
            next = new Node[level];
        }
    }
}

[Jetery]

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

class Node {

    int val;
    Node[] next_point;

    public Node(int val) {

        this.val = val;
    }
}

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

[mayloveless]

代码

class SkiplistNode {
    constructor(val, maxLevel) {
        this.val = val;
        this.forward = new Array(maxLevel).fill(0);
    }
}

const MAX_LEVEL = 32;
const P_FACTOR = 0.25;
var Skiplist = function() {
    this.head = new SkiplistNode(-1, MAX_LEVEL);
    this.level = 0;
};

Skiplist.prototype.search = function(target) {
    let curr = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
        /* 找到第 i 层小于且最接近 target 的元素*/
        while (curr.forward[i] && curr.forward[i].val < target) {
            curr = curr.forward[i];
        }
    }
    curr = curr.forward[0];
    /* 检测当前元素的值是否等于 target */
    if (curr && curr.val === target) {
        return true;
    } 
    return false;
};

Skiplist.prototype.add = function(num) {
    const update = new Array(MAX_LEVEL).fill(this.head);
    let curr = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
        /* 找到第 i 层小于且最接近 num 的元素*/
        while (curr.forward[i] && curr.forward[i].val < num) {
            curr = curr.forward[i];
        }
        update[i] = curr;
    }
    const lv = randomLevel();
    this.level = Math.max(this.level, lv);
    const newNode = new SkiplistNode(num, lv);
    for (let i = 0; i < lv; i++) {
        /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
        newNode.forward[i] = update[i].forward[i];
        update[i].forward[i] = newNode;
    }
};

Skiplist.prototype.erase = function(num) {
    const update = new Array(MAX_LEVEL).fill(0);
    let curr = this.head;
    for (let i = this.level - 1; i >= 0; i--) {
        /* 找到第 i 层小于且最接近 num 的元素*/
        while (curr.forward[i] && curr.forward[i].val < num) {
            curr = curr.forward[i];
        }
        update[i] = curr;
    }
    curr = curr.forward[0];
    /* 如果值不在存则返回 false */
    if (!curr || curr.val !== num) {
        return false;
    }
    for (let i = 0; i < this.level; i++) {
        if (update[i].forward[i] !== curr) {
            break;
        }
        /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
        update[i].forward[i] = curr.forward[i];
    }
    /* 更新当前的 level */
    while (this.level > 1 && !this.head.forward[this.level - 1]) {
        this.level--;
    }
    return true;
};

const randomLevel = () => {
    let lv = 1;
    /* 随机生成 lv */
    while (Math.random() < P_FACTOR && lv < MAX_LEVEL) {
        lv++;
    }
    return lv;
}

复杂度

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