首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
用单链表保存m个整数,结点的结构为:[dlata][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head
用单链表保存m个整数,结点的结构为:[dlata][link],且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表head
admin
2015-12-30
57
问题
用单链表保存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
学硕统考专业
相关试题推荐
传说中进行“绝地天通”的氏族首领是()。
第三次科技革命初期,苏联领先于美国的新兴科学技术成就是()。
三国时期,魏、蜀、吴灭亡的先后顺序是()。
有关石油的最早记载者是()
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
林则徐的反英国侵略的策略思想不包括()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
阅读材料,回答以下问题:今日中国独立自由的地位,已随不平等条约的撤废而获得。然而我们中国国民正确的反应,是义务感的激发与责任心的加强。国家的责任与国民的任务,从此更加重大。建国工作的完成,建国理想的实现,皆有待于我们的奋斗和牺牲。“天下无易事,天下无难事
明末清初,著名学者()抗清失败,前往日本讲学,传播中国文化。
随机试题
海关估价的方法。
Forthispart,youaresupposedtowritealetterofrefasalinEnglishin100-120wordsbasedonthefollowingsituation.Remem
男性,26岁,突起寒战、高热、咳嗽、胸痛,痰中带血丝,伴恶心、食欲不振,吸烟6年。X线胸片示:右上肺大片状密度一致阴影。WBC22×109/L,N89%,下列治疗应首选哪项最适宜
防治肥胖症的主要措施是
任何单位或个人认为专利局对某项专利权的授予不符合法律的,可以()。
张某被羁押8个月多,如果他就此项损害提出赔偿请求,那么赔偿义务机关应为()。对于人身受限制的损失,张某能够在何时期内提出国家赔偿请求方符合时效?()。
金融期货是以金融资产作为标的物的期货合约,下列属于金融期货的是()。Ⅰ外汇期货Ⅱ股指期权Ⅲ远期利率协议Ⅳ股指期货Ⅴ利率期货
接力项目,检录裁判应将接棒运动员带到()。
韩信拜将淮阴侯韩信者,淮阴人也。始为布衣时,贫,无行,不得推择为吏。常从人寄食饮,人多厌之者。尝数从其下乡南昌亭长寄食,数月,亭长妻患之,乃晨炊蓐食。食时,信往,不为具食。信亦知其义,怒,竞绝去。淮阴屠中少年有侮信者,曰:“若虽长大,好带刀
对互联网企业来讲,从用户那里收集到的信息主要包括消费习惯、行为特征、个人数据等,企业可以通过收集这些信息去开展大数据分析,进一步挖掘用户的潜在消费能力和更__________的价值,从而为用户提供更具__________的服务。填入画横线部分最恰当的一项是
最新回复
(
0
)