首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用单链表保存m个整数,结点的结构为:[data][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head如
用单链表保存m个整数,结点的结构为:[data][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head如
admin
2015-12-30
42
问题
用单链表保存m个整数,结点的结构为:[data][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head如下:
则删除结点后的head为:
要求:
给出算法的基本设计思想。
选项
答案
算法的基本设计思想 算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值,从而只需对链表进行一趟扫描。 因为|data|≤n,故辅助数组q的大小为n+1,各元素的初值均为0。依次扫描链表中的各结点,同时检查q[|data|]的值,如果为0,则保留该结点,并令q[|data|]=1;否则,将该结点从链表中删除。
解析
转载请注明原文地址:https://kaotiyun.com/show/YKxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列不属于凯末尔主义内容的是()。
马克思为第一国际起草的文件有()。①《共产党宣言》②《临时章程》③《成立宣言》④《资本论》
元代对边疆地区的统治方式不同于其他三地的一地是()。
北魏建立和统一的时间分别是()。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
中国古代的移民主要有两个大的流向:或者由北方草原内迁人中原,或者由中原迁入江南,这两大迁移最主要的影响是()。
汉灵帝中平元年(184),()在7州28郡同时俱起,这是中国历史上第一次组织、准备比较严密的农民起义。
论述世界反法西斯联盟的建立过程
论述斯巴达的阶级结构、政治制度和社会风尚
阅读下列史料,并回答问题:在琶勒尼斯(注:地名)一役获胜后,他(庇西特拉图)便占领政府,并解除人民武装;现在他已能稳定地握住僭主政权,并且取得那克索斯。以吕格达密斯为统治者。他解除人民武装的方法是这样的:他在塞修斯庙举行了一个武装的阅兵式,同时举行一次民
随机试题
下列不属于企业道德设计原则的是()
患儿男,7.5岁。上前牙外伤2小时,要求治疗。此上前牙的特点中错误的是
下列哪种情况不会见到血清钾增高
张某出差途中突发疾病死亡,被市社会保障局认定为工伤。但张某所在单位认为依据《工伤保险条例》,只有“在工作时间和工作岗位突发疾病死亡”才属于工伤,遂诉至法院。法官认为,张某为完成单位分配任务,须经历从工作单位到达出差目的地这一过程,出差途中应视为工作时间和工
水利工程建设总监理工程师实行()管理制度。
甲公司系上市公司,属于增值税一般纳税人,适用的增值税税率为17%;适用的所得税税率为25%。除特别说明外,甲公司采用账龄分析法计提坏账准备,3个月以内账龄的应收款项计提坏账准备的比率为0。甲公司按实现的净利润的10%提取法定盈余公积。甲公司20×
关于假性痴呆的特点,下列说法中不正确的是()。
【2014年陕西咸阳.判断】在班级管理中,班主任是班级的法人。()
参加大型团体表演的学生共300名,他们面对教练站成一排,从左到右按1、2、3、4、5……依次报数,教练要求全体学生牢记各自所报的数,并做下列动作:先让报的数是3的倍数的学生向后转;接着让报的数是5的倍数的学生向后转;最后让报的数是7的倍数的学生向后转,则此
A、TheywereprotectedbyastrongUnitedStatesNavy.B、Theyweresupportedbyawell-developedrailroadC、Mostcrewmembershad
最新回复
(
0
)