题目描述
不使用任何库函数，设计一个跳表
跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构
跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度更短，其设计思想与链表相似
例如，一个跳表包含 [30, 40, 50, 60, 70, 90]，然后增加 80、45 到跳表中，以下图的方式操作：
- 跳表中有很多层，每一层是一个短的链表
- 你的设计应该要包含这些函数：
-
void add(int num)：插入一个元素到跳表 -
bool search(int target)：返回 target 是否存在于跳表中。 -
bool erase(int num)：在跳表中删除一个值（num 不存在则返回 false，存在多个 num 则删除其中任意一个）
-
约束条件：
- 0 <= num, target <= 20000
- 最多调用 50000 次 search, add, 以及 erase操作。
样例：
数据结构
- 链表、跳表
算法思维
- 遍历
解题要点
- 类的设计（成员变量 与 成员方法）
- 跳表的性质与特点
关键知识点：跳表
• Skip List，跳跃表，简称跳表
• 实质是一种可以进行二分查找的链表
• 在原有的有序链表上面增加了多级索引，通过索引来实现快速查找，以空间换时间
跳表的特点
• 多层结构，每一层随机概率产生
• 每一层都是有序链表，默认升序，最底层包含所有元素，即原链表
• 每个节点包含两个指针：向右（right，同级链表）、向下（down，下级链表）
解题步骤
一. Comprehend 理解题意
题目主干要求
- 不能使用任何库函数
- 跳表由很多层有序的链表结构组成
- 最底层（Level 1）称为原链表，包含所有元素
- 上面每一层（Level i）链表都叫索引层，上级索引是下一级的子集
- 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现
- 每个节点包含两个指针，一个指向同一链表中的后一个元素，一个指向下面一层的元素
- 跳表的每一个操作都是从最高层链表的头节点开始，从左往右，从上往下
题目附加信息
- 添加元素允许重复
- 删除重复元素中的一个即可
- 添加元素后，用扔硬币的方式决定是否创建索引
- 删除元素时，应考虑索引的删除问题
- 跳表中存储的数据范围是：[0, 20000]
解题思路
- 跳表（Skiplist）类的成员：
- Node head：跳表的头节点指针
- void add(int num)：插入
- boolean search(int target)：查询
- boolean erase(int num)：删除
- 节点（Node）类的成员：
- int val：数据域
- Node right，down：指针域，向右，向下
二. Choose 选择数据结构与算法
数据结构：链表（多层链表组成跳表）
算法思维：遍历
三. Code 编码实现基本解法
步骤一：实现一个不含索引的跳表
- 创建跳表时初始化头节点和当前层级
head = HEAD; // -1，right = null，down = null - 完成查找功能 ：
boolean search(int target)找到返回 true
从 head 开始，从左到右、从上到下依次查找
如果 right 指向null，即尾节点，下移
如果节点值等于 target，返回
小于往右，大于往下 - 完成删除功能：
boolean erase(int num)删除成功返回 true
查找到要删除的元素，方式与 search 相同
执行删除操作：前面节点指向后面节点 - 完成插入功能：
void add(int num)插入原链表，支持重复
定位原链表中要插入的位置，方式与 search 相同，新元素放到重复元素后
新建节点，执行插入操作
class Skiplist {
final int HEAD_VALUE = -1; // 链表头节点的值
final Node HEAD = new Node(HEAD_VALUE);
Node head; // 最左上角的头节点，所有操作的开始位置
int levels; // 当前层级，即 head 节点所在的最高层数
public Skiplist() {
head = HEAD;
levels = 1;
}
class Node {
int val;
Node right, down;
Node(int val) {
this(val, null, null);
}
Node(int val, Node right, Node down) {
this.val = val;
this.right = right;
this.down = down;
}
}
public void add(int num) {
// 1.定位插入位置：原链表中 >= num 的最小节点前
Node node = head;
while(node != null) { // node==null，到达原链表
while(node.right != null && node.right.val < num) {
node = node.right;
}
if(node.down == null) {
break;
}
// 继续查找下一层的位置
node = node.down;
}
// 2.插入新节点
Node newNode = new Node(num, node.right, null);
node.right = newNode;
// 3.TODO 根据扔硬币决定（是否）生成索引
}
public boolean search(int target) {
Node n = head;
while(n != null) {
// 1.在同一层级上向右查找，直到链表的结尾
while(n.right != null && n.right.val < target) {
n = n.right;
}
// 2.若找到，返回true
Node right = n.right; // 要查找的节点
if(right != null && right.val == target) {
return true;
}
// 3.若右侧数据较大，向下一层
n = n.down;
}
return false;
}
public boolean erase(int num) {
boolean exist = false;
Node n = head;
while(n != null) {
// 2.获取该指定数据节点的前一个节点
while(n.right != null && n.right.val < num) {
n = n.right;
}
// 2.与当前层链表断开
Node right = n.right; // 要删除的节点
if(right != null && right.val == num) {
n.right = right.right;
right.right = null; // help GC
exist = true;
}
// 删除下一层
n = n.down;
}
return exist;
}
}
步骤二：实现有索引的插入和删除
- 完成删除功能：
下移，删除每一层 - 完成插入功能：
抛硬币生成（多层）索引：
正面朝上（随机数1），生成索引
背面朝上（随机数0），返回
索引层不存在，新建索引链表的头节点和索引节点
四. Consider 思考更优解
剔除无效代码，优化空间消耗
- 查找和删除方法定位元素的方式是相同的，可以优化
- 跳表的效率跟索引紧密相关，可以调整索引的生成策略来尝试优化
寻找更好的算法思维
- 借鉴其它算法
五. Code 编码实现最优解
class Skiplist {
//声明所需的成员变量
final int HEAD_VALUE = -1; //头节点值
Node head; //头节点
int levels; //跳表当前包括几层链表
int length; //跳表元链表的长度
public Skiplist() {
head = new Node(HEAD_VALUE);
levels = 1;
length = 1;
}
public void add(int num) {
//添加条件：当前正在遍历元链表 && 下一个节点的值不小于 num
Node curr = head;
Node[] nodes = new Node[levels]; //节点数组，存放每一个拐点
int i = 0; //计数器
//逐行遍历跳表，直到进入最底层
while (curr != null) {
//遍历当前层的每一个节点
while (curr.right != null && curr.right.val < num)
curr = curr.right;
//将拐点存入数组中
nodes[i++] = curr;
curr = curr.down;
}
//在元链表中插入新节点
curr = nodes[--i];
Node newNode = new Node(num, curr.right, null);
curr.right = newNode;
length++;
//添加索引，参数为：1.哪些节点上可能添加索引 2.当前为第几个节点 3.节点值
addIndex(newNode, nodes, i);
}
private void addIndex(Node target, Node[] nodeArray, int indices) {
Node downNode = target;
int coin = new Random().nextInt(2);
//添加索引的要求：硬币为1，且层数没有超过链表长度的 1/64
while (coin == 1 && levels < (length >> 6)) {
//没到达顶层前：在每一个拐点右侧添加新的索引节点
if (indices > 0) {
Node prev = nodeArray[--indices];
Node newIndex = new Node(target.val, prev.right, downNode);
prev.right = newIndex;
downNode = newIndex;
} else { //到达顶层后：添加新的一层，包括新的索引节点和一个新的头节点
Node newIndex = new Node(target.val, null, downNode);
head = new Node(HEAD_VALUE, newIndex, head);
levels++;
}
}
}
public boolean erase(int num) {
Node curr = get(num, head);
if (curr == null) return false;
//如果跳表中有当前元素，则逐行删除此节点
while (curr != null) {
Node right = curr.right;
curr.right = right.right;
right.right = null;
right.down = null;
//注意：这里只能使用 curr.down 而不能使用 curr，后者会报错
curr = get(num, curr.down);
}
length--;
return true;
}
public boolean search(int target) {
return get(target, head) != null;
}
private Node get(int target) {
return get(target, head);
}
private Node get(int target, Node from) {
Node curr = from;
//逐行遍历跳表
while (curr != null) {
//遍历当前行中的每一个节点，直到当前节点的下一个节点不小于 target
while (curr.right != null && curr.right.val < target)
curr = curr.right;
//循环结束后三种情况：right == target; right > target; right == null
if (curr.right != null && curr.right.val == target)
return curr;
curr = curr.down;
}
return null;
}
class Node {
int val;
Node right, down;
Node(int val) {
this(val, null, null);
}
Node(int val, Node right, Node down) {
this.val = val;
this.right = right;
this.down = down;
}
}
}
时间复杂度：O(log(n)) -- 二分查找 O(log(n))，查找+删除 O(log(n)) + O(k)，查找+插入 O(log(n)) + O(k)
空间复杂度：O(n) -- 元链表 O(n)，索引 O(n)
执行耗时：46 ms，击败了 35.10% 的Java用户
内存消耗：46.5 MB，击败了 21.30% 的Java用户
六. Change 变形与延伸
题目变形
- ConcurrentSkipListMap：TreeMap 的并发版本
- ConcurrentSkipListSet：TreeSet 的并发版本
- 给定一个链表，如何转成跳表结构？
延伸扩展
- Redis，LevelDB，Lucene
网友评论