the leetcode link

1206 设计跳表

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

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

例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：
skiplist

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

了解更多 : https://en.wikipedia.org/wiki/Skip_list

在本题中，你的设计应该要包含这些函数：

bool search(int target) : 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

示例 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 已被擦除

提示:

0 <= num, target <= 2 104
调用search, add, erase操作次数不大于 5 104

解题思路

  1. 设计Node，定义max_level，head ，level
  2. 通用步骤：枚举寻找目标所有层的前驱，过程是：先同层跳链表至前驱或尾节点，再进入下一层反复；
  3. 查询逻辑：在步骤2枚举过程中，一旦发现是前驱，则返回true；
  4. 删除逻辑：在步骤2枚举过程中，一旦发现是前驱，则同层的前驱指向其后驱，完成一次删除后进入下一层继续删除。优化：之后把可能产生的孤立头结点也删除；
  5. 插入逻辑：
  • 第1步，在步骤2枚举过程中，一旦发现是前驱的可能，则压栈；这将得到一个能从底层至高层弹出所有前驱可能的栈。
  • 第2步，先底层插入，才开始反复丢01硬币，概率性地从二层至高层插入新节点，以起始丢连续1的个数来控制插入多高层级，过程是：先不丢硬币，底层前驱出栈，新节点必插入在其后方，然后才开始丢硬币，决定是否插入次高一层，不插入则结束；如果要插入，就从栈取出当前层前驱，新节点插入在其后方形成连接，如果丢硬币运气太好，栈用完仍需插入，此时说明高度已超出原有层，则新建一层：新建头节点作为前驱，后方插入新节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class Skiplist {
    private final static int MAX_LEVEL = 32;  // 层级最大阈值

    class Node{
        int val;
        Node right; //指向同层的后驱
        Node down; //指向同节点的下一层，底层为空
        Node(int val, Node right, Node down){
            this.val = val;
            this.right = right;
            this.down = down;
        }
    }


    Node head; // 头节点

    int level; // 当前最大层级

    public Skiplist() {
        head = new Node(-1, null, null);
        level = 1;
    }

    public boolean search(int target) {
        Node node = head;
        while(node != null){
            while(node.right!=null && node.right.val<target) node = node.right;  // 同层跳链表,寻找当前层的前驱

            if(node.right!=null && node.right.val == target){
                return true;
            }

            node = node.down;  // 进下一层
        }
        return false;
    }

    public void add(int num) {
        // 1. 寻找新节点的所有符合条件的可能前驱节点，用栈记录下
        Deque<Node> prevStack = new ArrayDeque<>();

        Node node = head;
        while(node != null){
            while(node.right!=null && node.right.val<num) node = node.right;  // 同层跳链表,寻找当前层的前驱

            prevStack.push(node); // 高level到低level压栈 保存所有前驱节点

            node = node.down;  // 进下一层
        }

        // 2. 反复丢01硬币，决定插入新节点的level，底level必须插入，硬币初始化为1
        int coins = 1;  // 硬币初始化为1
        Random rand = new Random();

        Node prev = null, newNode = null;
        while(coins == 1 && level < MAX_LEVEL){
            if(!prevStack.isEmpty()){
                // 当有前驱，高level到低level弹栈
                prev = prevStack.pop();

            }else{
                // 当无前驱，则新建head作为前驱节点，level++
                head = new Node(-1, null, head);
                prev = head;
                level++;
            }
            //插入到当前层的链表上
            newNode = new Node(num, prev.right , newNode);
            prev.right = newNode;

            coins = rand.nextInt(2);  //丢硬币 [0,1]
        }
    }

    public boolean erase(int num) {
        boolean flag = false;
        Node node = head;
        while(node != null){
             while(node.right!=null && node.right.val<num) node = node.right;  // 同层跳链表,寻找当前层的前驱
            // 删除当前层的节点
            if(node.right!=null && node.right.val == num){
                flag = true;
                node.right = node.right.right;
            }

            node = node.down;  // 进下一层
        }
        // 删除孤立头节点
        while (level > 1 && head.right == null){
            head = head.down;
            level--;
        }

        return flag;
    }
}