【数据结构与算法】之深入解析“设计跳表”的求解思路与算法示例
【摘要】
一、题目要求
不使用任何库函数,设计一个 跳表,跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树,其功能与性能相当,并且跳表的代码长度相较下更短,其设计...
一、题目要求
- 不使用任何库函数,设计一个 跳表,跳表是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树,其功能与性能相当,并且跳表的代码长度相较下更短,其设计思想与链表相似。
- 例如,一个跳表包含 [30, 40, 50, 60, 70, 90] ,然后增加 80、45 到跳表中,以下图的方式操作:
- 跳表中有很多层,每一层是一个短的链表。在第一层的作用下,增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n)),空间复杂度是 O(n)。了解更多,请参考:Skip list。
- 在本题中,你的设计应该要包含这些函数:
-
- bool search(int target) : 返回 target 是否存在于跳表中;
-
- void add(int num): 插入一个元素到跳表;
-
- bool erase(int num): 在跳表中删除一个值,如果 num 不存在,直接返回false. 如果存在多个 num ,删除其中任意一个即可;
- 注意,跳表中可能存在多个相同的值,你的代码需要处理这种情况。
文章来源: blog.csdn.net,作者:╰つ栺尖篴夢ゞ,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/Forever_wj/article/details/124637215
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)