LeetCode 1206. 实现跳表

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

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

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

 

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

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

题目分析

跳表其实就是加了几层索引的链表，一共有 N 层，以 0 ~ N-1 层表示，设第 0 层是原链表，抽取其中部分元素，在第 1 层形成新的链表，上下层的相同元素之间连起来；再抽取第 1 层部分元素，构成第 2 层，以此类推。

为什么需要random函数呢？

需要某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。

如果你了解红黑树、AVL 树这样平衡二叉树，你就知道它们是通过左右旋的方式保持左右子树的大小平衡，而跳表是通过随机函数来维护前面提到的“平衡性”。

【查找】

跳表其实就是加了几层索引的链表，一共有 N 层，以 0 ~ N-1 层表示，设第 0 层是原链表，抽取其中部分元素，在第 1 层形成新的链表，上下层的相同元素之间连起来；再抽取第 1 层部分元素，构成第 2 层，以此类推。
具体选哪些元素呢？题目给的是coinFlip，也就是每次插入元素的时候，都进行一次 50% 概率的判断，如果 true 则向上层添加一个索引，如果 false 就不加了。

【添加和删除】

添加和删除的时候，存在数据重复的问题，经过我的测试，发现题目要求的是，将重复的数据当做不同的值来对待，即存了一个元素 9 ，再存一个 9 ，此时表里有俩 9 ，相互独立，删除一个 9 ，表里应该还剩余有一个9。

由于添加和删除元素都是从底层开始，而在查找的时候是从顶层开始查找的，因此可以使用一个数组记录每层的“跳跃节点”的位置，就不必反复的从顶层开始查找每层的位置了。

在添加的时候，首先是查找到添加位置，过程与查找类似，首先找到表中 >= 插入元素 的最小节点位置，然后插入节点， 50% 概率判别，如果需要添加索引，就添加索引，继续 50% 概率判别，直到结束。

在删除的时候，首先也是查找，找到表中所有 = 插入元素的节点位置（每层只找一个，找到直接跳层即可），然后挨个删除。

代码实现

class Skiplist {class SkipListNode {int val;int cnt;  // 当前val出现的次数SkipListNode[] levels;  // start from 0SkipListNode() {levels = new SkipListNode[MAX_LEVEL];}}private double p = 0.5;private int MAX_LEVEL = 16;private SkipListNode head;  // 头结点private int level;  // private Random random;public Skiplist() {// 保存此level有利于查询（以及其他操作）level = 0;  // 当前 skiplist的高度（所有数字 level数最大的）head = new SkipListNode();random = new Random();}// 返回target是否存在于跳表中public boolean search(int target) {SkipListNode curNode = head;for (int i = level-1; i >= 0; i--) {while (curNode.levels[i] != null && curNode.levels[i].val < target) {curNode = curNode.levels[i];}}curNode = curNode.levels[0];return (curNode != null && curNode.val == target);}// 插入一个元素到跳表。public void add(int num) {SkipListNode curNode = head;// 记录每层能访问的最右节点SkipListNode[] levelTails = new SkipListNode[MAX_LEVEL];for (int i = level-1; i >= 0; i--) {while (curNode.levels[i] != null && curNode.levels[i].val < num) {curNode = curNode.levels[i];}levelTails[i] = curNode;}curNode = curNode.levels[0];if (curNode != null && curNode.val == num) {// 已存在，cnt 加1curNode.cnt++;} else {// 插入int newLevel = randomLevel();if (newLevel > level) {for (int i = level; i < newLevel; i++) {levelTails[i] = head;}level = newLevel;}SkipListNode newNode = new SkipListNode();newNode.val = num;newNode.cnt = 1;for (int i = 0; i < level; i++) {newNode.levels[i] = levelTails[i].levels[i];levelTails[i].levels[i] = newNode;}}}private int randomLevel() {int level = 1;  // 注意思考此处为什么是 1 ？while (random.nextDouble() < p && level < MAX_LEVEL) {level++;}return level > MAX_LEVEL ? MAX_LEVEL : level;}// 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。public boolean erase(int num) {SkipListNode curNode = head;// 记录每层能访问的最右节点SkipListNode[] levelTails = new SkipListNode[MAX_LEVEL];for (int i = level-1; i >= 0; i--) {while (curNode.levels[i] != null && curNode.levels[i].val < num) {curNode = curNode.levels[i];}levelTails[i] = curNode;}curNode = curNode.levels[0];if (curNode != null && curNode.val == num) {if (curNode.cnt > 1) {curNode.cnt--;return true;}// 存在，删除for (int i = 0; i < level; i++) {if (levelTails[i].levels[i] != curNode) {break;}levelTails[i].levels[i] = curNode.levels[i];}while (level > 0 && head.levels[level-1] == null) {level--;}return true;} return false;}
}

代码实现二

class Skiplist {int MAX_LEVEL = 16;int curLevel;Node head;public Skiplist() {curLevel = 1;head = new Node(-1);head.next_point = new Node[MAX_LEVEL];}public boolean search(int target) {Node temp = head;//从最顶层索引找for (int i = MAX_LEVEL - 1; i >=0; i--) {while (temp.next_point[i] != null && temp.next_point[i].val <= target) {if (temp.next_point[i].val == target)return true;elsetemp = temp.next_point[i];}}// 判断temp的下个节点是否满足条件if (temp.next_point[0] != null && temp.next_point[0].val == target)return true;return false;}public void add(int num) {int level = randomLevel(0.5);if (level > curLevel)curLevel = level;Node node = new Node(num);node.next_point = new Node[level];Node[] forward = new Node[level];Arrays.fill(forward, head);Node temp = head;// 找到前驱节点for (int i = level - 1; i >= 0; i--) {while (temp.next_point[i] != null && temp.next_point[i].val < num)temp = temp.next_point[i];forward[i] = temp;}// 更新连接for (int i = 0; i < level; i++) {node.next_point[i] = forward[i].next_point[i];forward[i].next_point[i] = node;}}public boolean erase(int num) {Node[] forward = new Node[curLevel];Node temp = head;for (int i = curLevel - 1; i >= 0; i--) {while (temp.next_point[i] != null && temp.next_point[i].val < num)temp = temp.next_point[i];forward[i] = temp;}boolean res = false;if (temp.next_point[0] != null && temp.next_point[0].val == num) {res = true;// 更新连接for (int i = curLevel - 1; i >= 0; i--)if (forward[i].next_point[i] != null && forward[i].next_point[i].val == num)forward[i].next_point[i] = forward[i].next_point[i].next_point[i];}// 删除孤立节点层while (curLevel > 1 && head.next_point[curLevel - 1] == null)curLevel -= 1;return res;}public int randomLevel(double p) {int level = 1;while (Math.random() < p && level < MAX_LEVEL)level++;return level;}
}class Node {int val;Node[] next_point;public Node(int val) {this.val = val;}
}