跳表

• OI Wiki: https://oi-wiki.org/ds/skiplist/

题目	难度
1206. 设计跳表	困难

基本思想

跳表 (Skip List) 是由 William Pugh 发明的一种查找数据结构，支持对数据的快速查找，插入和删除。

跳表的期望空间复杂度为 O(n)，跳表的查询，插入和删除操作的期望时间复杂度都为 O(log n)。

1206. 设计跳表

import java.util.Arrays;
import java.util.Random;

public class Solution1206 {
    static class Skiplist {
        private static final int MAX_LEVEL = 32;
        // 以 p 的概率往上加一层，最后和上限值取最小。
        private static final double P = 0.25;
        private final Random random;
        private final SkiplistNode head;
        private int level;

        public Skiplist() {
            head = new SkiplistNode(-1, MAX_LEVEL);
            level = 0;
            random = new Random();
        }

        public boolean search(int target) {
            SkiplistNode cur = head;
            for (int i = level - 1; i >= 0; i--) {
                // 找到第 i 层小于且最接近 target 的元素
                while (cur.forward[i] != null && cur.forward[i].val < target) {
                    cur = cur.forward[i];
                }
            }
            cur = cur.forward[0];
            return (cur != null) && (cur.val == target);
        }

        public void add(int num) {
            SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
            Arrays.fill(update, head);
            SkiplistNode cur = head;
            for (int i = level - 1; i >= 0; i--) {
                // 找到第 i 层小于且最接近 num 的元素
                while (cur.forward[i] != null && cur.forward[i].val < num) {
                    cur = cur.forward[i];
                }
                update[i] = cur;
            }

            int lv = randomLevel();
            level = Math.max(level, lv);
            SkiplistNode newNode = new SkiplistNode(num, lv);
            for (int i = 0; i < lv; i++) {
                // 对第 i 层状态进行更新，将当前元素的 forward 指向新的节点
                newNode.forward[i] = update[i].forward[i];
                update[i].forward[i] = newNode;
            }
        }

        public boolean erase(int num) {
            SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
//            Arrays.fill(update, head);
            SkiplistNode cur = head;
            for (int i = level - 1; i >= 0; i--) {
                // 找到第 i 层小于且最接近 num 的元素
                while (cur.forward[i] != null && cur.forward[i].val < num) {
                    cur = cur.forward[i];
                }
                update[i] = cur;
            }
            cur = cur.forward[0];

            if (cur == null || cur.val != num) {
                return false;
            }
            for (int i = 0; i < level; i++) {
                if (update[i].forward[i] != cur) {
                    break;
                }
                update[i].forward[i] = cur.forward[i];
            }
            while (level > 1 && head.forward[level - 1] == null) {
                level--;
            }
            return true;
        }

        private int randomLevel() {
            int lv = 1;
            // nextDouble()方法用于从此随机数生成器的序列中获取下一个伪随机、均匀分布的双精度值，该值介于 0.0 和 1.0 之间。
            while (random.nextDouble() < P && lv < MAX_LEVEL) {
                lv++;
            }
            return lv;
        }

        private static class SkiplistNode {
            int val;
            SkiplistNode[] forward;

            public SkiplistNode(int val, int maxLevel) {
                this.val = val;
                this.forward = new SkiplistNode[maxLevel];
            }
        }
    }
}

（全文完）