🌕🌕🌕 1206. 设计跳表

难度: 🌕🌕🌕

问题描述

---

解法

class Skiplist {
    // 思路：
    // 1. 设置随机层数，最大层数为 32 层，所有节点肯定存在于 第一层
    // 2. 需要保存 当前跳表的最大层数
    int curMaxLevel;
    int maxLevel = 32; // 常数，层数范围为 [0, 31]
    double p = 0.5; // 要进入下一层的 概率
    Node head; // 虚拟头节点，存储 null 

    public Skiplist() {
        this.head = new Node(null, maxLevel);
        this.curMaxLevel = 1;
    }
    
    public boolean search(int target) {
        Node cur = head;
        for(int index = curMaxLevel - 1; index >= 0; index --) {
            Node pre = getNode(head, index, target);
            if(pre.nextArr[index] != null && pre.nextArr[index].val == target) {
                return true;
            }
        }
        // System.out.println("search");
        return false;
    }
    
    public void add(int num) {
        int level = getRandLevel();
        Node cur = head;
        Node node = new Node(num, level);
        for(int i = curMaxLevel - 1; i >= 0; i --) {
            cur = getNode(cur, i, num);
            if(i < level) {
                if(cur.nextArr[i] == null) {
                    cur.nextArr[i] = node;
                } else {
                    Node tmp = cur.nextArr[i];
                    cur.nextArr[i] = node;
                    node.nextArr[i] = tmp;
                }
            }
        }
        if(level > curMaxLevel) {
            for(int i = curMaxLevel; i < level; i ++) {
                head.nextArr[i] = node;
            }
            curMaxLevel = level;
        }
    }
    
    public boolean erase(int num) {
        boolean res = false;
        Node cur = head;
        for(int index = curMaxLevel - 1; index >= 0; index --) {
            Node pre = getNode(head, index, num);
            if(pre.nextArr[index] != null && pre.nextArr[index].val == num) {
                Node next = pre.nextArr[index].nextArr[index];
                pre.nextArr[index] = next;
                res = true;
            }
        }
        // System.out.println("erase");
        return res;
    }

    private int getRandLevel() {
        // 获取随机层数
        int res = 1; // 默认在第一层
        while(res < maxLevel && Math.random() < p) {
            res ++; // 升入上一层
        }
        return res;
    }

    private Node getNode(Node cur, int level, int val) {
        // 链表顺序向后查找
        while(cur.nextArr[level] != null && cur.nextArr[level].val < val) {
            cur = cur.nextArr[level];
        }
        return cur;
    }
}

class Node {
    Integer val; // 值，包装类
    Node[] nextArr; // 当前节点所在层数为 level，那么 [1, level] 的 next 节点均需要存储
    public Node(Integer val, int level) {
        this.val = val;
        nextArr = new Node[level];
    }
}

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

---

输出