跳表

概述

今天LeetCode的每日一题是设计一个跳表。跳表是一种类似链表的数据结构，可以实现时间复杂度为 O(log n) 的查找和插入，效率堪比红黑树。

常规的链表可以实现常数级时间复杂度的插入，但是查找某一个特定元素的元素却是线性的。而诸如数组和vector之类的简单线性的数据结构，虽然可以通过二分查找来实现 O(log n) 时间复杂度的查找，但是在某个特定位置插入一个元素需要把其后面所有元素都挪动一遍，牵一发而动全身。而AVL树、红黑树可以平衡插入和查找的效率，被广泛应用。今天刚学到的跳表也有相似的性质。

插一个小故事。就前两天我在看《STL源码剖析》试图理解红黑树的时候还看到一段话，说普通的链表查找某一个特定元素是线性的，我就想这个作者也太菜了，你不能二分查找吗？后来仔细一想，才想起来原来链表是没法随机访问的，自然不能二分查找，是我太菜了。

后来还是看不懂红黑树是什么原理。但是跳表就好理解多了。在LeetCode评论区里看到一条，“想了半天要如何确定一个值应该占用几层的链表，然后你给我来个coin filp，我遭不住了，底层逻辑基于随机数，怪不得STL里没你”，笑死我了。

扯了这么多，那么跳表到底是什么原理呢？用LeetCode上的一张图就可以看懂了。

查找

查找时从上往下依次找到每层小于目标值的最大的节点，然后依次往下查找，中间可以跳过很多个节点。因为可以有可以跳过节点这个性质，跳表查找的平均时间复杂度是O(log n) ，这个有大佬证明了，而我不是大佬所以我不会证明。

插入

插入时也依次从上往下找插入的节点，第0层包含跳表内的所有元素，然后每个元素在插入时有p的概率可以加入到上面那层，p 一般被设置为 1/2 。没错，跳表的结构是随机出来的，就是这么草率。

---

例题

LeetCode 1206. 设计跳表

就是设计一个上述跳表，要求实现查找、插入和删除三个功能。

示例 1：

输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]

解释
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 已被擦除

---

题解

class Skiplist {
private:
    class Node {
    //链表的节点类，把插入和删除的操作都集成进来了
    public:
        int val;
        vector<Node* > next = vector<Node* >(10, nullptr);//为了偷懒这里直接把十层链表的头尾节点都预留好了，内存击败百分五[ac01]
        Node(int v) :val(v) {};//构造函数
        void insert(Node* nxt, int level) {
            //在当前节点后面插入节点nxt，level代表目前操作的层数
            vector<Node* >& cur = this->next;
            nxt->next[level] = cur[level];
            cur[level] = nxt;
            return;
        }
        void erasenext(Node* nxt) {
            //在整个跳表中移除节点nxt
            vector<Node* >& cur = this->next;
            for (int i = 0; i < 10; i++) {
                if (cur[i] == nxt) {
                    cur[i] = cur[i]->next[i];
                }
            }
        }
    };
    //head和tail为头尾节点
    Node* head;
    Node* tail;
public:
    Skiplist() {
        //Skiplist类的构造函数，将head和tail进行初始化
        head = new Node(-1);
        tail = new Node(1e9 + 7);
        for (int i = 0; i < 10; i++) {
            //初始状态head的十个指针均应指向tail
            head->next[i] = tail;
        }
    }

    bool search(int target) {
        Node* cur = head;
        //从上往下依次找到每层比target小的最大节点
        for (int i = 9; i >= 0; i--) {
            while (cur->next[i]->val < target) cur = cur->next[i];
        }
        //如果最后一层的下一个节点的值不是target的话，那target一定不在跳表里。
        return cur->next[0]->val == target;
    }

    void add(int num) {
        /*前半部分和search过程一样
        只是需要多用一个stack把路上遇到的节点都存起来 */
        stack<Node* > stk;
        Node* cur = head;
        for (int i = 9; i >= 0; i--) {
            while (cur->next[i]->val < num) cur = cur->next[i];
            stk.push(cur);
        }
        int level = 0;
        Node* newnode = new Node(num);//创建新节点
        cur->insert(newnode, level);//第0层含有跳表全部元素，所以必须加入
        while (level < 9 && rand() % 2 == 0) {
            //进行一次判定，有1/2的几率可以进入上一层
            level++;
            stk.pop();
            stk.top()->insert(newnode, level);
        }
    }

    bool erase(int num) {
        //前半部分和add一样需要把路过的节点存起来
        stack<Node* > stk;
        Node* cur = head;
        for (int i = 9; i >= 0; i--) {
            while (cur->next[i]->val < num) cur = cur->next[i];
            stk.push(cur);
        }
        if (cur->next[0]->val != num) return false;//如果跳表里没有num就直接返回false
        else {
            /*否则调用erase函数删除后面一个节点
            此处传入的是节点的指针，保证不会误伤别的具有相同值的节点 */
            cur->erasenext(cur->next[0]);
            return true;
        }
    }
};

---

有的没的

暑假生活

暑假在家真的宅烂了，今天跟两个初中同学去南虹吃了一整天。吃了臭豆腐、老长沙手工肠、颜记排骨、虾滑、两杯茶百道、KFC、炸串串，饱死了。

没事听点歌（胡歌 - 忘记时间）