首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用单链表保存m个整数,结点的结构为:[dlata][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head
用单链表保存m个整数,结点的结构为:[dlata][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head
admin
2015-12-30
56
问题
用单链表保存m个整数,结点的结构为:[dlata][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head如下:
则删除结点后的head为:
要求:
给出算法的基本设计思想。
选项
答案
算法的基本设计思想 算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值,从而只需对链表进行一趟扫描。 因为|data|≤n,故辅助数组q的大小为n+1,各元素的初值均为0。依次扫描链表中的各结点,同时检查q[|data|]的值,如果为0,则保留该结点,并令q[|data|]=1;否则,将该结点从链表中删除。
解析
转载请注明原文地址:https://kaotiyun.com/show/XIRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
洪秀全以宗教手段组织起义,主要利用的是()。
传说中进行“绝地天通”的氏族首领是()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
下列历史事件发生的先后顺序是()①“铁幕”演说②马歇尔计划③北大西洋公约
前期罗马帝国时期,关于罗马东方行省的传统手工业产品的叙述,不正确的是()。
中国第一个资产阶级革命团体兴中会建立的时间是()。
电子计算机的发展经过了四代,①电子数值积分计算机(ENIAC);②集成电路计算机;③大规模集成电路计算机;④晶体管计算机;⑤人工智能计算机,其先后顺序是()。
20世纪30年代,美国推行“中立”的外交政策。对这一政策的正确表达是()。①适应国内外形势,维护自身利益②反映国际形势走向缓和③维护凡尔赛一华盛顿体系④不利于地区冲突的缓和与解决⑤不关心美洲地区以外的事务
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
随机试题
肝脂肪变性肝淤血
疔疮的病因病理内陷的病理
溶解氧含量可作为
居住在A市的张某因涉嫌挪用公款罪被人民检察院立案侦查并决定监视居住,张某因此应遵守下列哪些规定?()
砌体埋筋在隐蔽资料中有植筋内容的,必须做砌体埋筋的拉拔试验。()
由管理矿山企业的主管部门进行处理的是()。
工业用硬脂酸
Formanyparents,raisingateenagerislikefightingalongwar,butyearsgobywithoutanyclearwinner.Likeaborderconfli
依据《民政部、财政部关予加快推进社区社会工作服务的意见》要求,通过政府购买服务的方式,逐步将街道和乡镇政府面向社区的事务性、服务性工作委托有专业能力的社会组织承接。()
Thegovernmentofficialcanhardlyfindsufficientgroundsonwhichtobasehisargumentsin______(赞成修改税法).
最新回复
(
0
)