Google 2016 面试题5 岛屿计数2

Google2016面试题，附解答。...

(点击上方关注九章算法，获取最新IT求职干货！)

题目描述

给出一个m行n列的网格地图，每个位置为0或1，0表示海水1表示陆地。一开始地图全为0（没有陆地）。每次在一个位置加入一块陆地，返回此时地图中陆地的总块数（相邻陆地统计时为同一块陆地）。

Example:

操作#1: addLand(0, 0) turns the water at grid[0][0] into a land.



操作#2: addLand(0, 1) turns the water at grid[0][1] into a land.



操作#3: addLand(1, 2) turns the water at grid[1][2] into a land.



操作#4: addLand(2, 1) turns the water at grid[2][1] into a land.



返回答案数组:

[1, 1, 2, 3]

你可以做到复杂度O(k log mn)吗？其中k为操作次数。

分析解答

对于一个静态的地图，统计岛屿个数可以使用dfs（类似于寻找一个图中的连通块个数），算法复杂度是O(m*n)。但是对于一个不断更新的地图，如果我们每次重新统计连通块个数，复杂度为O(m*n*k)，其中k为总操作个数。考虑到每次只有一个位置发生变化（从0变为1），完全不必重新统一，该陆地的产生职能影响周围四个位置。假设该陆地周围有t（p至多为4）个不连通的岛屿，那么该陆地为把这四个不同点岛屿合并为一个岛屿，使得总岛屿数下降t-1个。因此我们需要维护岛屿之间的连通性，自然的我们想到了并查集。并查集是一种解决此类问题的强力数据结构，以此题为例，初始时每个位置都是独立的、互不连通的，每个位置都有一个标签来identify自己，记录在fa数组中，fa为i。当两个位置p、q相邻且都为1时，这两个位置需要统一它们的标签（表示这两个岛屿合并），即fa[p] = q。但是p、q的标签可能已经被修改，因此我们需要通过getfather函数递归找到它们的真实标签（getfather(i)的返回值也称为i的祖先），合并操作变为fa[getfather(p)] = getfather(q)。为了防止最坏情况下每次调用getfather函数都要经过m*n次递归，我们可以采用路径压缩的方法（详见代码中getfather函数），使得每个位置到其祖先的距离始终为一个很小的常数（与m、n无关）。本题中总体时间复杂度为O(m*n+k)，其中每次并查集的查询复杂度为一个常数（不超过4）。

参考代码

更多算法面试题答案：http://www.jiuzhang.com/solutions/



面试官角度分析

本题考查对数据结构并查集的了解和运用，给出正确算法可以达到hire。如果是用宽度优先搜索，那么只是暴力中等的水平。

LintCode相关题目练习

Google 2016 面试题4 | 矩阵中的最长上升路径

Google 2016 面试题3 | 摆动排序 II

Google 2016 面试题2 | 不构造树的情况下验证先序遍历

Google 2016 面试题1 | 数组补丁

关注公众号，回复类别关键字查看相关类别面试题集锦。关键字列表：动态规划，堆，哈希表，数组，二叉树，二分法，智力题，排序，概率，等等；

简介

九章算法,帮助更多中国人找到好工作!

九章算法，团队成员均为硅谷和国内顶尖IT企业工程师。提供算法培训、面试咨询、求职内推。

目前开设课程有九章算法班、系统设计班、Java入门与基础算法班、九章算法强化班。更有android/big data/ios 等即将开课。

目前培训的程序员遍布中国、美国、加拿大、澳大利亚、英国、新加坡等14个国家和地区。

更多详情，登录www.jiuzhang.com，或致信info@jiuzhang.com.

    关注 九章算法