本质是有序链表，只是不再是一条，而是有logN条

1206. 设计跳表

难度困难218收藏分享切换为英文接收动态反馈
不使用任何库函数，设计一个 跳表 。
跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。
例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：
跳表 - 图1
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。
了解更多 : https://en.wikipedia.org/wiki/Skip_list
在本题中，你的设计应该要包含这些函数：

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

提示:

  • 0 <= num, target <= 2 * 104
  • 调用search, add, erase操作次数不大于 5 * 104

思路：
使用多层有序链表
时间复杂度：插入，查询，删除都是O(logn)
空间复杂度：O(n)

  1. class Skiplist {
  2.     static final int level = 10;
  3.     class Node {
  4.         int val;
  5.         Node[] ne;
  6.         Node(int val) {
  7.             this.val = val;
  8.             ne = new Node[level];
  9.         }
  10.     }
  11.     void find(int target, Node[] res) {
  12.         Node p = head;
  13.         for (int i = level - 1; i >= 0; i--) {
  14.             while(p.ne[i] != null && p.ne[i].val < target)
  15.                 p = p.ne[i];
  16.             res[i] = p;
  17.         }
  18.     }
  20.     Node head = new Node(-1);
  21.     Node[] pre = new Node[level];
  22.     Random r = new Random();
  23.     public Skiplist() {}
  25.     public boolean search(int target) {
  26.         find(target, pre);
  27.         if (pre[0].ne[0] == null || pre[0].ne[0].val != target) return false;
  28.         return true;
  29.     }
  31.     public void add(int target) {
  32.         find(target, pre);
  33.         Node node = new Node(target);
  34.         for (int i = 0; i < level; i++) {
  35.             node.ne[i] = pre[i].ne[i];
  36.             pre[i].ne[i] = node;
  37.             if (r.nextInt(2) == 0) break;
  38.         }
  39.     }   
  41.     public boolean erase(int target) {
  42.         find(target, pre);
  43.         if (pre[0].ne[0] == null || pre[0].ne[0].val != target) return false;
  44.         for (int i = 0; i < level; i++) {
  45.             if (pre[i].ne[i] != null && pre[i].ne[i].val == target)
  46.                 pre[i].ne[i] = pre[i].ne[i].ne[i];
  47.         }
  48.         return true;
  49.     }
  50. }
  52. /**
  53.  * Your Skiplist object will be instantiated and called as such:
  54.  * Skiplist obj = new Skiplist();
  55.  * boolean param_1 = obj.search(target);
  56.  * obj.add(num);
  57.  * boolean param_3 = obj.erase(num);
  58.  */