网站系统繁忙是什么意思,李沧区网站服务公司,wordpress 映射 frp 群晖,seo工具是什么意思用单链表保存m个整数#xff0c;结点的结构为 [data] [link]#xff0c;且|data|n(n为正整数)。现要求设计一个时问复杂度尽可能高效的算法#xff0c;对于链表中 data 的绝对值相等的结点#xff0c;仅保留第一次出现的结点而删除其余绝对值相等的结点。例如#xff…用单链表保存m个整数结点的结构为 [data] [link]且|data|n(n为正整数)。现要求设计一个时问复杂度尽可能高效的算法对于链表中 data 的绝对值相等的结点仅保留第一次出现的结点而删除其余绝对值相等的结点。例如 若给定的单链表 head 如下则删除结点后的 head 为 给出算法的基本设计思想。使用采用C或C语言描述算法 给出单链表结点的数据类型定义。根据设计思想 采用C或C语言描述算法关键之处给出注释。说明你所设计算法的时间复杂度和空间算杂度。
方法一暴力求解
定义两个指针p指向21q指向-15p每走一步q就走剩下所有元素并比较相等就删除
时间O(m²) 空间O(1)
typedef struct Node
{int data; //该节点权值struct Node *link; //下一个节点
} Node;void ans(Node *HEAD)
{Node *p HEAD-link; //外层遍历节点pNode *q, *r; //q是r的前一个节点while (p ! NULL){q p;if (abs(r-data) abs(p-data)) //r表示待比较节点{q-link r-link;free(r);}else //不相同时才修改qq q-link;}p p-link;
}
方法二
算法的基本思想
算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的 数值从而只需对链表进行一趟扫描。 因为|data|≤n,故辅助数组 temp 的大小至少为 n1,各元素的初值均 0。依次扫描链表中的各结点同时检查 temp[|data|]的值如果为 0则 保留该结点并令temp[|data|]否则将该结点从链表中删除。
#include stdio.h
#include stdlib.h
#include limits.htypedef struct ListNode
{int data; //该节点权值struct Node *pNext; //下一个节点
} Node,*PNODE;//筛选链表中绝对值重复的元素
void FiltrateRep(PNODE L,int len)
{int temp[len];memset(temp,0,sizeof(int)*len);//初始化位0PNODE pre,p;preL;while(pre-pNext!NULL){ppre-pNext;if(p!NULL){if(temp[abs(p-data)]1){temp[abs(p-data)];//辅助数组对应元素位置1prep;}else{//如果temp[p-data]大于1,正在判断的元素是重复的元素需要删除pre-pNextp-pNext;free(p);}}}
}
