首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。 说明你所设计算法的时间复杂度与空间复杂度。
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
32
问题
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析:该算法除去链表本身外,只有O(1)的空间消耗。 时间复杂度分析:链表中不同的数值个数有O(n)个。该算法对每个不同的数值,都会对链表中的其他元素扫描一遍,并去掉重复的元素,这个过程的复杂度为O(n),所以整个算法的时间复杂度为O(n
2
)。
解析
转载请注明原文地址:https://kaotiyun.com/show/kexi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
布雷顿森林体系是如何建立的,包括哪些内容?
1993年,中共十四届三中全会上通过了《中共中央关于解决社会主义市场经济体制若干问题的决定》,其内容不包括()
《吕氏春秋》载:“公作则迟,有所匿其力也;分地则速,无所匿其力也。”这条材料反映的实质问题是()。
在19世纪60年代到90年代,洋务派兴办洋务事业的主要目的是()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
联共(布)“十五大”以后,新经济政策被逐步取消,根本上是由于()。
现今我国裕固族的祖先是()
“瓜步之战”发生在下列哪两个政权之间?()
随机试题
大体积混凝土工程主要掺入的外加剂是()。
试述配偶、血亲、姻亲关系的发生和终止的原因。
患者,女,42岁。心悸不宁,善惊易恐,坐卧不安,不寐多梦,易惊醒,恶闻声响,食少纳呆,苔薄白,脉细弦。其治法为
A.HBsAg(+)、HBeAg(-)、抗HBc(+)B.HBsAg(-)、抗HBs(+)、抗HBc(+)C.HBsAg(+)、HBeAg(+)、HBV-DNA(+)D.HBsAg(+)、HBeAg(-)、HBV-DNA(-)E.H
A.氯喹B.甲硝唑C.乙胺嘧啶D.吡喹酮E.伯氨喹主要用于疟疾预防的药物是()。
在讲解“相向而行的行程问题"时,教师在幻灯片上画一条线段表示两地间的距离,并出示两个小人,通过幻灯机显示在屏幕上.教师的这种教学方法属于().
“周郎妙计安天下,赔了夫人又折兵”这一典故出自《三国演义》。其中“夫人”是指()。
【四等人制】扬州大学2014年中国史真题;西北民族大学2015年中国史综合真题
以下关于配置IP访问控制列表的描述中,哪个是错误的?——
______thatmyheadhadcleared,mybrainwasalsobeginningtoworkmuchbetter.
最新回复
(
0
)