跳表
设计跳表- 粗暴的说 跳表就是一张二维表 这张表用二分的思想把所有的元素的
半存了起来 方便我们查询 - 所以相交于传统的n的时间复杂度 降到了logn
- 但是空间复杂度 也上升了 因为我们需要把所有的元素的
半存起来 - 所以跳表的空间复杂度 是nlogn
- 理论上用二维数组也可以编写 但是我门还是采用数组+链表的形式 因为简单
- 同样 这次使用ts来实现 放弃rust, rust写这个不用unsafe得死！
//创建node 里面存储一个值 和一个数组保存 半 值
class TNode {
val: number
next: TNode[];
constructor(_val: number,level:number) {
this.val = _val
this. next: TNode[] = new Array<TNode>(level)
}
}- 我们需要一个level 来确定当前层级 因为主要是写lc 所以设置为10
- 实际使用的话 可以使用设计的最大容量来折算 maxLevel=log₂n
- 同时为了方便处理 我们使用-1作为头结点
class Skiplist {
he: TNode = new TNode(-1)
level: number = 10
}函数编写
- find是整个设计的核心 他的作用是找到t在每一层的位置 方便我们进行增删查
- 我们从最大的level开始 找到每一层小于t的最大的数 然后把这个数的下一个数存起来
- 这样我们就找到了t在每一层的位置
- 然后我们就可以进行增删查了
find(t: number): Array<TNode> {
let cur = this.he
let ns: TNode[] = new Array<TNode>(this.level)
for (let i = this.level - 1; i >= 0; i--) {
while (cur.next[i] != null && cur.next[i].val < t){
cur = cur.next[i];
}
ns[i] = cur;
}
return ns
}- 这里我们通过find找到t在每一层的位置
- 之后找到ns中的第一个数 如果这个数不为空 并且这个数的值等于t 那么就返回true
search(t: number): boolean {
let ns= this.find(t)
return ns[0].next[0] != null && ns[0].next[0].val == t
}- 这里我们通过find找到t在每一层的位置
add(t: number): void {
let ns= this.find(t)
const node = new TNode(t,this.level)
for (let i = 0; i < this.level; i++) {
node.next[i] = ns[i].next[i]
ns[i].next[i] = node
//这里使用随机数来决定是否向上增长
if (Math.round(Math.random()) == 0) break
}
} erase(t: number): boolean {
let ns= this.find(t)
const node = ns[0].next[0]
if (node == null || node.val != t) return false
for (let i = 0; i < this.level && ns[i].next[i] == node; i++){
ns[i].next[i] = ns[i].next[i].next[i]
}
return true
}- 这里留一个扣子，如果是string或者其他的类型甚至是引用数据类型 我们该如何做处理呢？
跳表
展开查看
点击展开答案...