题目形容

这是 LeetCode 上的 1206. 设计跳表 ，难度为 艰难。

Tag : 「链表」、「数据结构」

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

跳表 是在 $O(log{n})$ 工夫内实现减少、删除、搜寻操作的数据结构。跳表相比于树堆与红黑树，其性能与性能相当，并且跳表的代码长度相较下更短，其设计思维与链表类似。

例如，一个跳表蕴含 [30, 40, 50, 60, 70, 90]，而后减少 80、45 到跳表中，以下图的形式操作：

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，减少、删除和搜寻操作的工夫复杂度不超过 $O(n)$。跳表的每一个操作的均匀工夫复杂度是 $O(\log{n})$，空间复杂度是 $O(n)$。

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

  • 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);   // 返回 falseskiplist.add(4);skiplist.search(1);   // 返回 trueskiplist.erase(0);    // 返回 false，0 不在跳表中skiplist.erase(1);    // 返回 trueskiplist.search(1);   // 返回 false，1 已被擦除

提醒:

  • $0 <= num, target <= 2 \times 10^4$
  • 调用 search, add,  erase 操作次数不大于 $5 \times 10^44$

数据结构

对于单链表而言，所有的操作（增删改查）都遵循「先查找，再操作」的步骤，这导致在单链表上所有操作复杂度均为 $O(n)$（瓶颈在于查找过程）。

跳表绝对于单链表，则是通过引入「多层」链表来优化查找过程，其中每层链表均是「有序」链表：

  • 对于单链表的 Node 设计而言，咱们只需存储对应的节点值 val，以及以后节点的下一节点的指针 ne 即可（ne 为一指针变量）
  • 对于跳表来说，除了存储对应的节点值 val 以外，咱们须要存储以后节点在「每一层」的下一节点指针 ne（ne 为指针数组）

跳表的 level 编号从下往上递增，最上层的链表为元素最全的有序单链表，而查找过程则是依照 level 从上往下进行。

操作次数的数据范畴为 $n = 5 \times 10^4$，因而设计最大的 level 为 $\log{n}$ 即可确保复杂度，但因为操作次数 $n = 5 \times 10^4$ 不可能全是 add 操作，因而这里间接取 level 为 $10$。

同时为了简化，建设一个哨兵节点 he，哨兵值的值该当足够小（依据数据范畴，设定为 $-1$ 即可），所有的操作（假如以后操作的传入值为 t），先进行统一化的查找：查找出每一层比 t 严格小的最初一个节点，将其存成 ns 数组。即 $ns[i]$ 为 $level = i$ 层严格比 $t$ 小的最初一个节点。

再依据不同的操作进行下一步动作：

  • search 操作：因为最初一层必然是元素最全的单链表，因而能够间接拜访 ns[0].ne[0] 即是所有元素中满足大于等于 t 的第一个元素，通过判断其值与传入值 t 的大小关系来决定后果；
  • add 操作：因为最初一层必然是元素最全的单链表，因而咱们「从下往上」进行插入，最底下一层必然要插入，而后以一半的概率往上传递；
  • erase 操作：与 add 操作互逆，依照「从下往上」的程序进行删除。须要留神的是，因为雷同的值在跳表中可能存在多个，因而咱们在「从下往上」删除过程中须要判断待删除的元素与 ns[0].ne[0] 是否为同一元素（即要判断地址是否雷同，而不是值雷同）。

Java 代码：

class Skiplist {    int level = 10;    class Node {        int val;        Node[] ne = new Node[level];        Node (int _val) {            val = _val;        }    }    Random random = new Random();    Node he = new Node(-1);    void find(int t, Node[] ns) {        Node cur = he;        for (int i = level - 1; i >= 0; i--) {            while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i];            ns[i] = cur;        }    }    public boolean search(int t) {        Node[] ns = new Node[level];        find(t, ns);        return ns[0].ne[0] != null && ns[0].ne[0].val == t;    }    public void add(int t) {        Node[] ns = new Node[level];        find(t, ns);        Node node = new Node(t);        for (int i = 0; i < level; i++) {            node.ne[i] = ns[i].ne[i];            ns[i].ne[i] = node;            if (random.nextInt(2) == 0) break;        }    }    public boolean erase(int t) {        Node[] ns = new Node[level];        find(t, ns);        Node node = ns[0].ne[0];        if (node == null || node.val != t) return false;        for (int i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i];        return true;    }}

TypeScript 代码：

const level: number = 10class TNode {    val: number    ne: TNode[] = new Array<TNode>(level)    constructor(_val: number) {        this.val = _val    } }class Skiplist {    he: TNode = new TNode(-1)    find(t: number, ns: TNode[]): void {        let cur = this.he        for (let i = level - 1; i >= 0; i--) {            while (cur.ne[i] != null && cur.ne[i].val < t) cur = cur.ne[i]            ns[i] = cur        }    }    search(t: number): boolean {        let ns: TNode[] = new Array<TNode>(level)        this.find(t, ns)        return ns[0].ne[0] != null && ns[0].ne[0].val == t    }    add(t: number): void {        let ns: TNode[] = new Array<TNode>(level)        this.find(t, ns)        const node = new TNode(t)        for (let i = 0; i < level; i++) {            node.ne[i] = ns[i].ne[i]            ns[i].ne[i] = node            if (Math.round(Math.random()) == 0) break        }    }    erase(t: number): boolean {        let ns: TNode[] = new Array<TNode>(level)        this.find(t, ns)        const node = ns[0].ne[0]        if (node == null || node.val != t) return false        for (let i = 0; i < level && ns[i].ne[i] == node; i++) ns[i].ne[i] = ns[i].ne[i].ne[i]        return true    }}
  • 工夫复杂度：所有操作的复杂度瓶颈在于 find 查找，find 查找冀望复杂度为 $O(\log{n})$
  • 空间复杂度：$O(n)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.1206 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地

本文由mdnice多平台公布