【leetcode】305. Number of Islands II

1 必须有个deepcopy才行,这样才不会修改原来的matrix中的值

2 上述方法时间复杂度是O(kmn),自然超时了

3 union find方法:在此题中,坐标(x,y)做为一个node,对于positions中的每一个position,都创建一个一对一的map,map的key和value都是这个坐标

4 对于每一个position,count每次加1,同时检查其上下左右,如果属于同一个union,相当于每次合并则count-1

5 union(x,y)的时候,如果x,y的root node是同一个,则直接返回0

6 接下来是根据x和y的rank来进行union


union find: 初始化时都初始化成自己,比如此题中,x和parent[x]都初始化成position的坐标

rank都初始化成0

检查当前点的上下左右坐标,看两个点是否是union在一起的


一定要判断这个,因为如果之前出现过的position

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 原题 给定 n,m,分别代表一个2D矩阵的行数和列数,同时,给定一个大小为 k 的二元数组A。起初,2D矩阵的行数...
    Jason_Yuan阅读 1,518评论 0 0
  • <center>#1 Two Sum</center> link Description:Given an arr...
    铛铛铛clark阅读 2,203评论 0 3
  • --- layout: post title: "如果有人问你关系型数据库的原理,叫他看这篇文章(转)" date...
    蓝坠星阅读 824评论 0 3
  • 同学: 你好!我提起笔给你写信,我既紧张,又高兴,不知道说什么好!我十分紧张:那是因为我不知道,你会不会拒绝...
    金奕彤阅读 692评论 0 0
  • 欢迎来到Crazy 超链接智能系统,你好我是Crazy 团队创始人 ,在没和大家加好友情况下,只能与这种方式和大家...
    Crazy韩金俊阅读 600评论 0 0