Week8 命题作业((伪)代码描述两个单向链表找合并元素的算法并给出时间复杂度、HDFS 之 DataNode 宕机处理时序图)

用户头像
星河寒水
关注
发布于: 8 小时前
Week8命题作业((伪)代码描述两个单向链表找合并元素的算法并给出时间复杂度、HDFS之DataNode宕机处理时序图)

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用(伪)代码描述算法,并给出时间复杂度。

  • 方法一:蛮力法

开始;
链表1长度m,链表2长度n
p1指针指向链表1头结点head1,p2指针指向链表2头结点head2
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if (p2->data==p1->data)
{
输出p1->data;
break;
}
p2=p1->next;
}
p1=p1->next;
}
结束;

因为有嵌套for循环,所以时间复杂度为O(mn)

  • 方法二:利用栈的概念

  • 结合题目可知,链表若有合并,其元素从尾开始,肯定至少有一个合并的节点是尾结点,然后依次往头推进比较,若遇到两节点不同(不是合并的),则输出前一次合并的元素即为解

  • 由于是单向链表,要取得尾结点只能遍历得到,若要从尾开始只能初始化两个栈,将两个链表的元素分别压入各自的栈空间里,由栈的“后进先出”特点,可以做到从尾部开始比较

开始;
初始化栈1 s1;
初始化栈2 s2;
p1指针指向链表1头结点head1,p2指针指向链表2头结点head2;
do {
StackPush(s1,p1->data);
p1=p1->next;
}while(p1->next!=NULL);
do {
StackPush(s2,p2->data);
p2=p2->next;
}while(p2->next!=NULL);
初始化lastEqualData记录最新的合并元素
x1=StackPop(s1);
x2=StackPop(s2);
while(x1!=null&&x1==x2){
lastEqualData=x1;
if (StackIsEmpty(s1))
x1=null;
else
x1=StackPop(s1);
if (StackIsEmpty(s2))
x2=null;
else
x2=StackPop(s2);
}
输出lastEqualData;
结束;

由伪代码3个循环体可知,无嵌套循环,故时间复杂度为O(m+n)

请画出 DataNode 服务器节点宕机的时候,HDFS 的处理过程时序图。



发布于: 8 小时前 阅读数: 23
用户头像

星河寒水

关注

还未添加个人签名 2018.09.17 加入

还未添加个人简介

评论

发布
暂无评论
Week8命题作业((伪)代码描述两个单向链表找合并元素的算法并给出时间复杂度、HDFS之DataNode宕机处理时序图)