搜索
写经验 领红包
 > 职场

跳表数据结构与算法(跳表结构的实现)

导语:设计跳表 和数据结构实现题

跳表数据结构与算法(跳表结构的实现)

题目描述

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

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

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

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

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

跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(logn),空间复杂度是 O(n)在本题中,你的设计应该要包含这些函数:

bool search(int target): 返回 target 是否存在于跳表中。void add(int num): 插入一个元素到跳表。bool erase(int num): 在跳表中删除一个值,如果 num 不存在,直接返回 false. 如果存在多个 num ,删除其中任意一个即可。

注意,跳表中可能存在多个相同的值,你的代码需要处理这种情况。

示例 1:

输入[&34;, &34;, &34;, &34;, &34;, &34;, &34;, &34;, &34;, &34;][[], [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×104调用 search, add, erase 操作次数不大于 5×1044

数据结构

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

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

对于单链表的 Node 设计而言,我们只需存储对应的节点值 val,以及当前节点的下一节点的指针 ne 即可(ne 为一指针变量)对于跳表来说,除了存储对应的节点值 val 以外,我们需要存储当前节点在「每一层」的下一节点指针 ne(ne 为指针数组)

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

操作次数的数据范围为n=5×104,因此设计最大的 level 为 logn 即可确保复杂度,但由于操作次数 n=5×104 不可能全是 add 操作,因此这里直接取 level 为 10。

同时为了简化,建立一个哨兵节点 he,哨兵值的值应当足够小(根据数据范围,设定为 −1 即可),所有的操作(假设当前操作的传入值为 t),先进行统一化的查找:查找出每一层比 t 严格小的最后一个节点,将其存成 ns 数组。即 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(logn)空间复杂度:O(n)

本文内容由小春整理编辑!