首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。 说明你所设计算法的时间复杂度与空间复杂度。
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
26
问题
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
空间复杂度分析:该算法除去链表本身外,只有O(1)的空间消耗。 时间复杂度分析:链表中不同的数值个数有O(n)个。该算法对每个不同的数值,都会对链表中的其他元素扫描一遍,并去掉重复的元素,这个过程的复杂度为O(n),所以整个算法的时间复杂度为O(n
2
)。
解析
转载请注明原文地址:https://kaotiyun.com/show/kexi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
第一国际成立于下面的哪个城市?()
试总结苏联二三十年代社会主义建设的特点、成就及存在的问题
继承并发展德谟克利特和伊壁鸠鲁的“原子论”,认为宇宙万物都是由原子构成的,并按照物质本身所特有的规律发展的罗马共和国时期的哲学家()。
蒙古军西征之后,罗斯处于()的控制之下。
反映查理大帝进攻阿拉伯人控制的西班牙的文学作品是()。
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
第一国际成立的时间是()。
我国第一部系统的史学理论著作是()。
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
随机试题
A.抑制气道变应性炎症B.抑制炎症细胞,预防变应原引起速发和迟发反应C.舒缓支气管,减少分泌物分泌D.迅速松弛支气管平滑肌E.收缩支气管平滑肌,增强呼吸肌收缩,增强黏膜纤毛功能色甘酸钠治疗哮喘作用机制
下列各项中哪一项用pKb表示
商务谈判胜负的决定性因素在于()。
徐某1990年曾因投机倒把罪被判5年有期徒刑,服刑期间经过减刑,于1994年11月刑满释放。1998年,徐某在某市开设一娱乐城,自任总经理,为谋利,非法提供色情服务。为了对付公安机关的查处和管理卖淫妇女,徐某要求统一保管卖淫妇女的身份证,对卖淫妇女实行集体
施工单位在编制施工方案时,可能发生施工机械选择不当、流水施工安排不合理等问题,由此可能导致施工延误和一些质量问题,这种风险属于风险类型中的()。
容许建筑高度是指()。
金融衍生工具交易一般只需要支付少量的保证金或权利金就可签订远期大额合约或互换不同的金融工具指的是金融衍生工具的()特性。
甲公司2×18年至2×20年的有关交易或事项如下:(1)2×18年1月1日,甲公司以银行存款购入乙公司的一项房地产(办公楼)。取得增值税专用发票上注明的价款为1800万元,增值税税额为162万元。甲公司于当日与丁公司签订租赁合同,将购入的房地产出租给丁公
下列关于内部控制评价的说法中,正确的是()。
(演示文稿题)在某动物保护组织就职的张宇要制作一份介绍世界动物日的PowerPoint演示文稿。按照下列要求,完成演示文稿的制作。为演示文稿插入幻灯片编号,编号从1开始,标题幻灯片中不显示编号。
最新回复
(
0
)