1206. 设计跳表

题目描述：

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

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

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

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 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 已被擦除

限制及提示：

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

---

解题分析及思路：

这一题先不看题目的要求怎么去设计跳表，而是去完成这几个方法，你就会发现其实算不上困难题。

可以采用一个map去存储num再这个跳表中的个数，插入时，个数加一，删除时，个数减一即可

构造Skiplist结构体，并初始化

type Skiplist struct {
	nums map[int]int
}

func Constructor() Skiplist {
	return Skiplist{
		make(map[int]int),
	}
}

定义三个方法，对map进行取值后判断即可。

func (this *Skiplist) Search(target int) bool {
	if count, ok := this.nums[target]; ok && count > 0 {
		return true
	}
	return false
}

func (this *Skiplist) Add(num int) {
	this.nums[num]++
}

func (this *Skiplist) Erase(num int) bool {
	if count, ok := this.nums[num]; ok && count > 0 {
		this.nums[num]--
		return true
	}
	return false
}

复杂度：

• 时间复杂度：O(1)
• 空间复杂度：O(n)

执行结果：

• 执行用时： 36 ms, 在所有 Go 提交中击败了100.00%的用户
• 内存消耗：9.5 MB, 在所有 Go 提交中击败了57.56% 的用户