跳表

const double PFACTOR = 0.25;
const int MAX_LEVEL = 32;
class Skiplist {
    struct Node {
        int val;
        vector<Node*> forward;
        Node(int _val, int level): val(_val), forward(level, nullptr) {
        }
    };
    random_device rd;
    mt19937 gen{rd()};
    uniform_real_distribution<double> dis{0, 1};
public:
    Node* head;
    int level;
    Skiplist() {
        head = new Node(-1, MAX_LEVEL);
        level = 0;
    }
    bool search(int target) {
        Node *cur=this->head;
        for(int i=level-1; i>=0; i--) {
            while(cur->forward[i] && cur->forward[i]->val < target) {
                cur = cur->forward[i];
            }
        }
        cur = cur->forward[0];
        return cur && cur->val == target;
    }
    void add(int num) {
        int lv=randomLv();
        level=max(level, lv);
        array<Node*, MAX_LEVEL> shouldupdate;
        Node *cur=this->head;
        for(int i=level-1; i>=0; i--) { // 找到各层要更新的结点
            while(cur->forward[i] && cur->forward[i]->val < num) {
                cur = cur->forward[i];
            }
            shouldupdate[i] = cur; // 虽然全部记录了但是并不是全部都用了
        }
        Node *newNode=new Node(num, lv);
        for(int i=0; i<lv; i++) { // 只有前Lv层（结点所在那些层级）的前序节点才会被更新
            newNode->forward[i] = shouldupdate[i]->forward[i];
            shouldupdate[i]->forward[i] = newNode;
        }
         return;
    }
    
    bool erase(int num) {
        array<Node*, MAX_LEVEL> shouldupdate;
        Node *cur=this->head;
        for(int i=level-1; i>=0; i--) {
            while(cur->forward[i] && cur->forward[i]->val < num) {
                cur = cur->forward[i];
            }
            shouldupdate[i] = cur;
        }
        cur = cur->forward[0]; // 最底层再推进一次应该就是要删除的元素
        if (!(cur && cur->val == num)) return false; // 说明当前skiplist不存在该元素
        // 从最底0层开始更新前序节点，直到没有这个元素的层数上
        for(int i=0; i<level && shouldupdate[i]->forward[i]==cur; i++) {
            shouldupdate[i]->forward[i] = cur->forward[i];
        }
        delete cur; // 删除节点本身
        while(level>1 && !head->forward[level-1]) { // 如果删除节点使得顶上几层变为了空，我们需要删除顶上这些层
            level--;
        }
        return true;
    }
private:
    int randomLv() {
        int lv=1;
        while(dis(gen)<PFACTOR && lv<MAX_LEVEL) lv++;
        return lv;
    }
};

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

Donate