2015年408算法题
【摘要】
1
）算法的基本设计思想
算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行
一趟扫描。
因为
|data|
≤n，故辅助数组 q 的大小为 n+1，各元素的初值均为 0。依次扫描链表中的各结点，同
时检查 q[|data|]的值，如果为 0，则保留该结点，并令 q[|data|]...
1 ）算法的基本设计思想 算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行 一趟扫描。 因为 |data| ≤n，故辅助数组 q 的大小为 n+1，各元素的初值均为 0。依次扫描链表中的各结点，同 时检查 q[|data|]的值，如果为 0，则保留该结点，并令 q[|data|]=1；否则，将该结点从链表中删除。
-
-
typedef struct node{
-
int data;
-
struct node *link;
-
}NODE;
-
typedef NODE *PNODE;
-
-
void func (PNODE h,int n){
-
PNODE p=h,r;
-
int *q,m;
-
q=(int *)malloc(sizeof(int)*(n+1));//申请n+1个位置的辅助空间
-
for(int i=0;i<n+1;i++) //数组元素初值置为0
-
*(q+i)=0;
-
while(p->link!=NULL)
-
{
-
m=p->link->data>0?p->link->data:-p->link->data;
-
if(*(q+m)==0) //判断该结点的data是否已出现过
-
{
-
*(q+m)=1; //首次出现
-
p=p->link; //保留
-
}
-
else{ //重复出现
-
r=p->link; //删除
-
p->link=r->link;
-
free(r);
-
}
-
}
-
free(q);
-
}
-
算法的时间复杂度为 O(m) ，空间复杂度为 O(n) 。
文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。
原文链接：andyguo.blog.csdn.net/article/details/103414802
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）