设计跳表
不使用任何库函数,设计一个跳表。
跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树,其功能与性能相当,并且跳表的代码长度相较下更短,其设计思想与链表相似。
例如,一个跳表包含 [30, 40, 50, 60, 70, 90],然后增加 80、45 到跳表中,以下图的方式操作:
Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons
跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n)),空间复杂度是 O(n)。
在本题中,你的设计应该要包含这些函数:
bool search(int target) : 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值,如果 num 不存在,直接返回false. 如果存在多个 num ,删除其中任意一个即可。
了解更多 : https://en.wikipedia.org/wiki/Skip_list
注意,跳表中可能存在多个相同的值,你的代码需要处理这种情况。
样例:
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 <= 20000
最多调用 50000 次 search, add, 以及 erase操作。
struct Node{ Node *right,*down; //向右向下足矣 int val; Node(Node *right,Node *down,int val):right(right),down(down),val(val){} }; class Skiplist { private: Node *head; public: Skiplist() { head=new Node(NULL,NULL,-1); //初始化头结点 } bool search(int target) { Node *p=head; while(p){ while(p->right && p->right->val<target){ //寻找目标区间,基本就是这个思路 p=p->right; } if(!p->right || target<p->right->val){ //没找到目标值,则继续往下走 p=p->down; }else{ //找到目标值,结束 return true; } } return false; } void add(int num) { vector<Node*> pathList; //从上至下记录搜索路径 Node *p=head; while(p){ while(p->right && p->right->val<num){ p=p->right; } pathList.push_back(p); p=p->down; } bool insertUp=true; Node* downNode=NULL; while(insertUp && pathList.size()>0){ //从下至上搜索路径回溯,50%概率 Node *insert=pathList.back(); pathList.pop_back(); insert->right=new Node(insert->right,downNode,num); //add新结点 downNode=insert->right; //把新结点赋值为downNode insertUp=(rand()&1)==0; //50%概率 } if(insertUp){ //插入新的头结点,加层 head=new Node(new Node(NULL,downNode,num),head,-1); } } bool erase(int num) { Node *p=head; bool seen=false; while(p){ while(p->right && p->right->val<num){ p=p->right; } if(!p->right ||p->right->val>num){ p=p->down; }else{ //搜索到目标结点,进行删除操作,结果记录为true,继续往下层搜索,删除一组目标结点 seen=true; p->right=p->right->right; p=p->down; } } return seen; } };
1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。