2. 考研
  3. 用单链表保存m个整数，结点的结构为：[dlata][link]，且｜data｜≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head

用单链表保存m个整数，结点的结构为：[dlata][link]，且｜data｜≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head

admin2015-12-30  43
问题 用单链表保存m个整数，结点的结构为：[dlata][link]，且｜data｜≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表head如下：

则删除结点后的head为：

要求：
给出算法的基本设计思想。
选项
答案算法的基本设计思想 算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。 因为｜data｜≤n，故辅助数组q的大小为n+1，各元素的初值均为0。依次扫描链表中的各结点，同时检查q[｜data｜]的值，如果为0，则保留该结点，并令q[｜data｜]=1；否则，将该结点从链表中删除。
解析
转载请注明原文地址:https://jikaoti.com/ti/KkfjFFFM
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)