写点什么

第八作业

用户头像
Binary
关注
发布于: 2021 年 01 月 17 日
  1. 有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

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


分析

两个链表,如果发生合并,后面的元素则一定相同。从头开始,找出两个链表第一次匹配的位置,依次往后比较,如果全部相同,则认为可以合并。

思路一,穷举法

问题是要寻找两个链表的合并节点,那么第一个直观的想法就是穷举法。顺序对第一个链表中的每一个节点,查看其在第二个链表中是否存在;若存在,则说明该节点就是两个链表的第一个合并点;若找不到,则说明两个链表没有合并。这个算法的时间复杂度为 O(m*n)。伪代码如下。


思路二,以空间换时间

在第一个思路中,我们很容易发现,第二个链表被检查过很多遍,最坏情况(找不到合并点)下对每个节点都查找了一遍。那能不能在查找一遍就把结果记在某个地方,以后直接查找而不用在遍历一遍呢?

在很多编程语言中都有 Dictionary 这种数据结构,它的一个特点就是查询的时间复杂度是 O(1),即用 key 可以直接查得结果。Dictionary 是用哈希算法实现这个 O(1)复杂度的查询。假设哈希算法时间开销相比这个链表查询开销小很多的话,可以用 Dictionary 和下面的算法来解决问题,时间复杂度和空间复杂度都是 O(m+n)。伪代码如下。


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


用户头像

Binary

关注

还未添加个人签名 2018.04.27 加入

还未添加个人简介

评论

发布
暂无评论
第八作业