leetcode1206. 设计跳表

题目

题解

• search 操作：由于最后一层必然是元素最全的单链表，因此可以直接访问 ns[0].ne[0] 即是所有元素中满足大于等于 t 的第一个元素，通过判断其值与传入值 t 的大小关系来决定结果；

• add 操作：由于最后一层必然是元素最全的单链表，因此我们「从下往上」进行插入，最底下一层必然要插入，然后以一半的概率往上传递；

• erase 操作：与 add 操作互逆，按照「从下往上」的顺序进行删除。需要注意的是，由于相同的值在跳表中可能存在多个，因此我们在「从下往上」删除过程中需要判断待删除的元素与 ns[0].ne[0] 是否为同一元素（即要判断地址是否相同，而不是值相同）

作者：宫水三叶

链接：https://leetcode.cn/problems/design-skiplist/solutions/1698876/by-ac_oier-38rd/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Skiplist {
public:
    static const int level = 10;
    struct Node{
        int val;
        vector<Node*> next;
        Node(int _val):val(_val){
            next.resize(level, nullptr);
        }
    }*head;
    Skiplist() {
        head = new Node(-1);
    }
    ~Skiplist(){
        delete head;
    }
    void find(int target, vector<Node*>&pre){
        Node* p = head;
        for(int i = level-1; i >= 0; i--){
            while(p->next[i] && p->next[i]->val < target)p = p->next[i];
            pre[i] = p;
        }
    }
    bool search(int target) {
        vector <Node*>pre (level);
        find(target, pre);
        auto p = pre[0]->next[0];
        return p && p->val==target;
    }
    
    void add(int num) {
        vector<Node*>pre(level);
        find(num, pre);
        auto p = new Node(num);
        for(int i = 0; i < level; i++){
            p->next[i] = pre[i]->next[i];
            pre[i]->next[i] = p;
            if(rand()%2)break;
        }
    }
    
    bool erase(int num) {
        vector<Node*> pre(level);
        find(num, pre);
        auto p = pre[0]->next[0];
        if(!p || p->val != num) return false;
        for(int i =0; i<level && pre[i]->next[i] == p; i++){
            pre[i]->next[i] = p->next[i];
        }
        delete p;
        return true;
    }
};

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