跳表

• OI Wiki: https://oi-wiki.org/ds/skiplist/

题目	难度
1206. 设计跳表	困难

基本思想

跳表 (Skip List) 是由 William Pugh 发明的一种查找数据结构，支持对数据的快速查找，插入和删除。

跳表的期望空间复杂度为 O(n)，跳表的查询，插入和删除操作的期望时间复杂度都为 O(log n)。

1206. 设计跳表

import java.util.Arrays; import java.util.Random;  public class Solution1206 {  static class Skiplist {  private static final int MAX_LEVEL = 32;  // 以 p 的概率往上加一层，最后和上限值取最小。  private static final double P = 0.25;  private final Random random;  private final SkiplistNode head;  private int level;   public Skiplist() {  head = new SkiplistNode(-1, MAX_LEVEL);  level = 0;  random = new Random();  }   public boolean search(int target) {  SkiplistNode cur = head;  for (int i = level - 1; i >= 0; i--) {  // 找到第 i 层小于且最接近 target 的元素  while (cur.forward[i] != null && cur.forward[i].val < target) {  cur = cur.forward[i];  }  }  cur = cur.forward[0];  return (cur != null) && (cur.val == target);  }   public void add(int num) {  SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];  Arrays.fill(update, head);  SkiplistNode cur = head;  for (int i = level - 1; i >= 0; i--) {  // 找到第 i 层小于且最接近 num 的元素  while (cur.forward[i] != null && cur.forward[i].val < num) {  cur = cur.forward[i];  }  update[i] = cur;  }   int lv = randomLevel();  level = Math.max(level, lv);  SkiplistNode newNode = new SkiplistNode(num, lv);  for (int i = 0; i < lv; i++) {  // 对第 i 层状态进行更新，将当前元素的 forward 指向新的节点  newNode.forward[i] = update[i].forward[i];  update[i].forward[i] = newNode;  }  }   public boolean erase(int num) {  SkiplistNode[] update = new SkiplistNode[MAX_LEVEL]; // Arrays.fill(update, head);  SkiplistNode cur = head;  for (int i = level - 1; i >= 0; i--) {  // 找到第 i 层小于且最接近 num 的元素  while (cur.forward[i] != null && cur.forward[i].val < num) {  cur = cur.forward[i];  }  update[i] = cur;  }  cur = cur.forward[0];   if (cur == null || cur.val != num) {  return false;  }  for (int i = 0; i < level; i++) {  if (update[i].forward[i] != cur) {  break;  }  update[i].forward[i] = cur.forward[i];  }  while (level > 1 && head.forward[level - 1] == null) {  level--;  }  return true;  }   private int randomLevel() {  int lv = 1;  // nextDouble()方法用于从此随机数生成器的序列中获取下一个伪随机、均匀分布的双精度值，该值介于 0.0 和 1.0 之间。  while (random.nextDouble() < P && lv < MAX_LEVEL) {  lv++;  }  return lv;  }   private static class SkiplistNode {  int val;  SkiplistNode[] forward;   public SkiplistNode(int val, int maxLevel) {  this.val = val;  this.forward = new SkiplistNode[maxLevel];  }  }  } }

（全文完）