LintCode 题解丨FLAG大厂经典面试题:岛屿的个数II

简介: LintCode 题解丨FLAG大厂经典面试题:岛屿的个数II

给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组A. 初始二维矩阵全0. 二元数组A内的k个元素代表k次操作, 设第i个元素为 ​(A[i].x, A[i].y)​, 表示把二维矩阵中下标为A[i].x行A[i].y列的元素由海洋变为岛屿. 问在每次操作之后, 二维矩阵中岛屿的数量. 你需要返回一个大小为k的数组.

设定0表示海洋, 1代表岛屿, 并且上下左右相邻的1为同一个岛屿.
在线评测地址:LintCode 领扣

样例 1:
输入: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]
输出: [1,1,2,2]
解释:

  1. 00000

    00000
    00000
    00000
  2. 00000

    01000
    00000
    00000
  3. 01000

    01000
    00000
    00000
  4. 01000

    01000
    00000
    00010
  5. 01000

    01000
    00000
    00011

    样例 2:

输入: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]
输出: [1,1,2,2]
方法一:暴力做法

每次操作后做一遍bfs
枚举之前未访问过的岛屿,岛屿数量加一
压入队列中开始bfs
从bfs的队列中取出队首,上下左右四个方向扩展那些没有访问过的岛屿,扩展之后压入队列中
重复执行第四步,一直到队列为空
这样从一个岛屿出发,搜索了它能到的所有岛屿,这些岛屿将合并成一个大岛屿
重新回到第二步
方法二:并查集维护

并查集是指用集合里的一个元素来当这个集合的代表元

如果两个元素所在集合的代表元相同,那么我们就能知道这两个元素在一个集合当中。

如果我们想合并两个集合,只需要把其中一个集合的代表元改为第二个集合的代表元

这道题中,每次将一个海洋i变成一个岛屿i,那么先将岛屿数量加一
再依次查看这个岛屿的四周的四个方格
如果相邻的方格j也是岛屿,那么先判断i是不是和j在同一个集合里
如果不是在一个集合里,那么i j所在的两个集合就是连通的,可以合并算为一个集合,然后让岛屿数量-1。
如果已经是在同一个集合里了,那就不用在进行任何操作
我们只要让i所在集合的代表元改为j所在集合的代表元就完成了合并操作。
注意:数据中有可能多次将一个位置变成岛屿,第一次以后的操作都是无效的操作,跳过就好了
注意2:x->x1->x2->x3->x4->x5->x6->........->代表元T
我们在第一次寻找x的代表元的回溯的时候

顺便把这条路径的所有xi的父亲改为了代表元T

这样我们以后再次访问x....x6....T这条链上的内容时候就可以很快的得到答案

//伪代码for i 1:n

fa[i]=i //伪代码,一开始让所有的父亲都是本身

//我们规定代表元的父亲为本身,如果一个节点的父亲不是本身,说是它在一个元素个数大于1的集合中,而且这个节点并不是代表元

function find(x) //寻找x所在集合的代表元

if(fa[x]==x)

return x; //x是代表元,直接返回

else

return fa[x]=find(fa[x]) //x不是代表元,寻找x的父亲的代表元是谁,并且直接把代表元赋值给x的父亲

function uniue(x,y)//合并两个集合

fa[find(x)]=find(y)

复杂度分析

时间复杂度

暴力做法

每次操作都会做一遍bfs ,做一遍bfs的时间复杂度是O(NM)

所以总时间复杂度是 O(KNM),K是操作次数,NM是地图长和宽

并查集

每次查询代表元均摊是O(α) α代表反阿克曼函数,反阿克曼函数是渐进增长很慢很慢的,我们可以近似的认为每次查询是O(1)的复杂度 我们一共有K次操作,每次操作最多并查集查询4次,并查集合并4次,所以我们最终的时间复杂度是O(K)的

空间复杂度

n,m是输入数组 的长和宽

我们需要一个fa数组大小为nm,一个vis数组(标记该点有没有变成岛屿),所以空间复杂度是O(nm)

public class Solution {

/**
 * @param n: An integer
 * @param m: An integer
 * @param operators: an array of point
 * @return: an integer array
 */

public int find(int []fa, int x) {
    if(x == fa[x]) {
        return x;
    } else {
        return fa[x] = find(fa, fa[x]);
    }
}
public int calc(int x, int y, int n, int m) {
    return x * m + y;
}
public List<Integer> numIslands2(int n, int m, Point[] operators) {

    // write your code here
    List<Integer> ans = new ArrayList<>();
    int [] fa = new int [n * m + 5];
    Map<Integer, Boolean>visited = new HashMap<Integer, Boolean>();
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            fa[calc(i, j, n, m)] = calc(i, j, n, m);
            visited.put(calc(i, j, n, m), false);
        }
    }
    //行走数组,用于遍历i岛屿的四周四个方向的岛屿下标
    int[] zx = {0, 0, 1, -1};
    int[] zy = {1, -1, 0, 0};

    if(operators == null) {
        return ans;
    }
    for(int i = 0; i < operators.length; i++) {

        int x = operators[i].x, y = operators[i].y;
        // 第i次操作的点 已经是岛屿了,跳过就好了
        if(visited.get(calc(x, y, n, m)) == true) {
            ans.add(cnt);
            continue;
        }
        //第i次操作的点 出现了新的岛屿
        cnt++;
        //遍历这个岛屿的四周四个方向
        for(int k = 0; k < 4; k++) {
            int nx = x + zx[k];
            int ny = y + zy[k];
            //判断往四周走有没有走越界,或者走到海洋里,越界或者走到海洋都是没有的状态
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited.get(calc(nx, ny, n, m)) == false) {
                continue;
            }
            //判断四周的岛屿是不是和当前第i次操作的岛屿 已经在一个集合了
            if(find(fa, calc(x, y, n, m)) == find(fa, calc(nx, ny, n, m))) {
                continue;
            }
            /*
            如果不是在一个集合里,那么i j所在的两个集合就是连通的,可以合并算为一个集合,然后让岛屿数量-1。
            我们只要让i所在集合的代表元改为j所在集合的代表元就完成了合并操作
            */
            else {
                cnt--;
                fa[find(fa, calc(x, y, n, m))] = find(fa, calc(nx, ny, n, m));
            }
        }
        //标记它是个岛屿
        visited.put(calc(x, y, n, m), true);
        ans.add(cnt);
    }
    return ans;
}

}
更多题解参考:

九章算法 - 帮助更多中国人找到好工作,硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

相关文章
|
自然语言处理
[leetcode/lintcode 题解]大厂面试真题详解: 电话号码的字母组合
[leetcode/lintcode 题解]大厂面试真题详解: 电话号码的字母组合
[leetcode/lintcode 题解]大厂面试真题详解: 电话号码的字母组合
[leetcode/lintcode 题解] 国内大厂面试高频题: 数组除了自身的乘积
[leetcode/lintcode 题解] 国内大厂面试高频题: 数组除了自身的乘积
[leetcode/lintcode 题解] 国内大厂面试高频题: 数组除了自身的乘积
[leetcode/lintcode 题解] 阿里面试高频题:岛屿的个数
[leetcode/lintcode 题解] 阿里面试高频题:岛屿的个数
[leetcode/lintcode 题解]  阿里面试高频题:岛屿的个数
[leetcode/lintcode 题解]国内大厂面试真题详解:摊平二维向量
[leetcode/lintcode 题解]国内大厂面试真题详解:摊平二维向量
[leetcode/lintcode 题解]国内大厂面试真题详解:摊平二维向量
|
自然语言处理 搜索推荐
[leetcode/lintcode 题解] 国内大厂面试真题详解:外星人字典
[leetcode/lintcode 题解] 国内大厂面试真题详解:外星人字典
[leetcode/lintcode 题解]  国内大厂面试真题详解:外星人字典
|
存储 算法
[leetcode/lintcode 题解]大厂算法面试高频题: 序列化和反序列N叉树
[leetcode/lintcode 题解]大厂算法面试高频题: 序列化和反序列N叉树
[leetcode/lintcode 题解]大厂算法面试高频题: 序列化和反序列N叉树
|
算法 搜索推荐
[leetcode/lintcode 题解] 算法面试真题详解:安排面试城市
[leetcode/lintcode 题解] 算法面试真题详解:安排面试城市
[leetcode/lintcode 题解]  算法面试真题详解:安排面试城市
|
机器学习/深度学习
[leetcode/lintcode 题解] 阿里巴巴面试真题:数组评分
[leetcode/lintcode 题解] 阿里巴巴面试真题:数组评分
[leetcode/lintcode 题解]  阿里巴巴面试真题:数组评分