一、题目

1、题目描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

2、基础框架

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        
    }
};

3、原题链接

200. 岛屿数量

二、解题报告

1、思路分析

1. 方法一：使用递归
   遍历每个位置，如果当前位置是1，则将四个方位（上下左右）相连的1都修改为2（感染过程），以保证最终递归可终止。一旦发现了一个 1 字符，发现了一个岛屿，感染的次数也就是岛屿的个数。
2. 方法二：使用并查集
   将每个1视作单独的集合，遇到一个 1 就考虑它的左边和上边是否为1，如果是1，则放到同一个集合中。重点在将不同位置的 1 视作单独的集合，所以问题就在于如何将这些 1 区分开。
   两种实现方法：
   • 使用一个 Dot 空类，利用该类的实例来区分值相同的情况
   • 将 $m\ast n$ 矩阵的元素全部放到一个长度为 $m\ast n$ 的数组中，其中 $(i,j)$ 位置的元素放到一维数组 i * 列数 + j 下标处。

2、时间复杂度

$O(mn)$

3、代码详解

/*************************************************************************
	> File Name: 049.Leetcode200_岛屿数量.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 四  7/28 22:19:40 2022
 ************************************************************************/

#include <iostream>
#include <unordered_map>
#include <vector>
#include <stack>
#include <ctime>
using namespace std;

//方法一：使用递归，也是最优解
//时间复杂度O(m*n)
//主流程中每个位置被遍历1遍，而在infect过程中，每个位置被它的上下左右邻居访问到，最多4遍，所以每个位置最多被访问5遍，所以时间复杂度是O(mn)
class Solution1 {
public:
    void infect(vector<vector<char> > &grid, int i, int j) {
        //检查越界
        if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size() || grid[i][j] != '1') {
            return ;
        }
        
        //相邻四个方位的1全部都改成2
        grid[i][j] = 2;
        infect(grid, i - 1, j);
        infect(grid, i + 1, j);
        infect(grid, i, j - 1);
        infect(grid, i, j + 1);
    }

    int numIslands(vector<vector<char> >& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        int islandsCnt = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    islandsCnt++;
                    infect(grid, i, j);
                }
            }
        }

        return islandsCnt;
    }
};


//方法二：使用并查集，用一个类的实例区分值相同元素
class Solution2 {
public:
    class Dot {};

    template <class V>
    class Node {
    public:
        V value;
        Node(V v) : value(v) {}
    };

    template <class V>
    class UnionFind {
    private:
        //V 对应的节点
        unordered_map<V, Node<V>*> nodes;
        // 节点V 对应的父节点
        unordered_map<Node<V>*, Node<V>*> parents;
        //代表节点V所在集合的元素个数
        unordered_map<Node<V>*, int> sizeMap;
    public:    
        UnionFind(vector<V> &values) {
            for (V val : values) {
                Node<V> *node = new Node<V>(val);
                nodes[val] = node;
                parents[node] = node;
                sizeMap[node] = 1;
            }
        }


        Node<V> *find(Node<V> *cur) {
            stack<Node<V>*> path;
            while (cur != parents[cur]) {
                path.push(cur);
                cur = parents[cur];
            }

            while (!path.empty()) {
                parents[path.top()] = cur;
                path.pop();
            }

            return cur;
        }
    public:
        void myUnion(V &a, V &b) {
            Node<V> *aHead = find(nodes[a]);
            Node<V> *bHead = find(nodes[b]);

            if (aHead != bHead) {
                int aSetSize = sizeMap[aHead];
                int bSetSize = sizeMap[bHead];
                Node<V> *big = aSetSize >= bSetSize ? aHead : bHead;
                Node<V> *small = big == aHead ? bHead : aHead;

                parents[small] = big;
                sizeMap[big] = aSetSize + bSetSize;
                sizeMap.erase(small);
            }
        }

        int setSize() {
            return sizeMap.size();
        }
    };

    int numIslands(vector<vector<char> >& grid) {
        int row = grid.size();
        int col = grid[0].size();

        vector<vector<Dot*> > dots(row, vector<Dot*>(col));
        vector<Dot*> dotArray;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    dots[i][j] = new Dot();
                    dotArray.push_back(dots[i][j]);
                }
            }
        }

        UnionFind<Dot*> *uf = new UnionFind<Dot*>(dotArray);
        for (int i = 1; i < col; i++) {
            if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
                uf->myUnion(dots[0][i - 1], dots[0][i]);
            }
        }

        for (int j = 1; j < row; j++) {
            if (grid[j - 1][0] == '1' && grid[j][0] == '1') {
                uf->myUnion(dots[j - 1][0], dots[j][0]);
            }
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (grid[i][j] == '1') {
                    if (grid[i - 1][j] == '1') {
                        uf->myUnion(dots[i][j], dots[i - 1][j]);
                    }

                    if (grid[i][j - 1] == '1') {
                        uf->myUnion(dots[i][j], dots[i][j - 1]);
                    }
                }
            }
        }

        return uf->setSize();
    }
};

//方法三：使用并查集，将原二维数组中的元素放到一维数组中
class Solution3 {
public:
    class UnionFind {
    private:
        vector<int> parents;
        vector<int> size;
        vector<int> help;
        int col; //列数
        int setSize; //集合个数

    public:
        UnionFind(vector<vector<char> > &grid) {
            col = grid[0].size();
            setSize = 0;
            int row = grid.size();
            int len = row * col;
            parents.resize(len);
            size.resize(len);
            help.resize(len);
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == '1') {
                        int ind = index(i, j);
                        parents[ind] = ind;
                        size[ind] = 1;
                        setSize++;
                    }
                }
            }
        }

    private:
    	//(r,c) 位置的元素放到一维数组中的位置就是 r * col + c
        int index(int r, int c) {
            return r * col + c;
        }

        int find(int i) {
            int hi = 0;
            while (i != parents[i]) {
                help[hi++] = i;
                i = parents[i];
            }

            for (hi--; hi >= 0; hi--) {
                parents[help[hi]] = i;
            }

            return i;
        }
    public:
        void myUnion(int r1, int c1, int r2, int c2) {
            int ind1 = index(r1, c1), ind2 = index(r2, c2);
            int f1 = find(ind1), f2 = find(ind2);
            if (f1 != f2) {
                if (size[f1] >= size[f2]) {
                    parents[f2] = f1;
                    size[f1] += size[f2];
                } else {
                    parents[f1] = f2;
                    size[f2] += size[f1];
                }
                setSize--;
            }
        }
        
        int setCnt() {
            return setSize;
        }
    };


    int numIslands(vector<vector<char> >& grid) {
        int row = grid.size();
        int col = grid[0].size();

        UnionFind *uf = new UnionFind(grid);
        
		//单独处理第0行
        for (int i = 1; i < col; i++) {
            if (grid[0][i - 1] == '1' && grid[0][i] == '1') {
                uf->myUnion(0, i - 1, 0, i);
            }
        }
		//单独处理第0列
        for (int j = 1; j < row; j++) {
            if (grid[j - 1][0] == '1' && grid[j][0] == '1') {
                uf->myUnion(j - 1, 0, j, 0);
            }
        }
		
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (grid[i][j] == '1') {
                    if (grid[i - 1][j] == '1') {
                        uf->myUnion(i, j, i - 1, j);
                    }

                    if (grid[i][j - 1] == '1') {
                        uf->myUnion(i, j, i, j - 1);
                    }
                }
            }
        }

        return uf->setCnt();
    }
};

//测试代码
vector<vector<char> > generateRandomMatrix(int row, int col) {
    vector<vector<char> > board(row, vector<char>(col));
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            board[i][j] = (rand() % 100 / (double)101) < 0.5 ? '1' : '0';
        }
    }

    return board;
}

vector<vector<char> > copy(vector<vector<char> > &board) {
    int row = board.size();
    int col = board[0].size();
    vector<vector<char> > ans(row, vector<char>(col));
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            ans[i][j] = board[i][j];
        }
    }
    return ans;
}


int main() {
    srand(time(0));
    int row = 0;
    int col = 0;
    vector<vector<char> > board1;
    vector<vector<char> > board2;
    vector<vector<char> > board3;

    long long start = 0;
    long long end = 0;

    row = 1000;
    col = 1000;
    board1 = generateRandomMatrix(row, col);
    board2 = copy(board1);
    board3 = copy(board1);

    cout << "感染方法、并查集(map实现)、并查集(数组实现) 的运行结果和运行时间:" << endl;
    cout << "随机生成的二维矩阵规模 : " << row << " * " << col << endl;

    Solution1 s1;
    Solution2 s2;
    Solution3 s3;
    start = clock();
    cout << "感染方法运行结果： " << s1.numIslands(board1) << endl;;
    end = clock();
    cout << "感染方法运行时间：" << (end - start) * 1000 / CLOCKS_PER_SEC <<  " ms" << endl;


    start = clock();
    cout << "并查集（map实现）运行结果： " << s2.numIslands(board2) << endl;;
    end = clock();
    cout << "并查集（map实现）运行时间：" << (end - start) * 1000 / CLOCKS_PER_SEC << " ms" << endl;


    start = clock();
    cout << "并查集（数组实现）运行结果： " << s3.numIslands(board3) << endl;;
    end = clock();
    cout << "并查集（数组实现）运行时间：" << (end - start) * 1000 / CLOCKS_PER_SEC << " ms" << endl;

	row = 10000;
    col = 10000;
    board1 = generateRandomMatrix(row, col);
    board3 = copy(board1);

    cout << "感染方法、并查集(map实现)、并查集(数组实现) 的运行结果和运行时间:" << endl;
    cout << "随机生成的二维矩阵规模 : " << row << " * " << col << endl;

    start = clock();
    cout << "感染方法运行结果： " << s1.numIslands(board1) << endl;;
    end = clock();
    cout << "感染方法运行时间：" << (end - start) * 1000 / CLOCKS_PER_SEC <<  " ms" << endl;

    start = clock();
    cout << "并查集（数组实现）运行结果： " << s3.numIslands(board3) << endl;;
    end = clock();
    cout << "并查集（数组实现）运行时间：" << (end - start) * 1000 / CLOCKS_PER_SEC << " ms" << endl;

    return 0;
}

三、小结

随机的一组测试数据运行结果：

感染方法、并查集(map实现)、并查集(数组实现) 的运行结果和运行时间:
随机生成的二维矩阵规模 : 1000 * 1000
感染方法运行结果： 61488
感染方法运行时间：71 ms
并查集（map实现）运行结果： 61488
并查集（map实现）运行时间：4218 ms
并查集（数组实现）运行结果： 61488
并查集（数组实现）运行时间：120 ms
感染方法、并查集(map实现)、并查集(数组实现) 的运行结果和运行时间:
随机生成的二维矩阵规模 : 10000 * 10000
感染方法运行结果： 6139131
感染方法运行时间：6249 ms
并查集（数组实现）运行结果： 6139131
并查集（数组实现）运行时间：12105 ms

可以注意到，并查集使用map实现的方式比使用数组实现的方式慢得多，二者虽然时间复杂度相同，但是使用map实现的常数更大，所以时间上花的更多。

四、扩展：如果 matrix 极大，设计一种可行的并行计算方案

【思路】上述的遍历方案通常是基于单CPU和单内存的，如果matrix 极大，这个方案已近行不通了。
例子：假设现在是2个CPU，将矩阵分为2块：计算每块的岛屿数量，同时记录第一个 1 出现的以及边界上该位置的2是由什么位置感染而得，可得左边部分的岛屿数量为 2：

同理，右边部分的岛屿数量也为2：

那么一共岛屿数量是4。

然后就只关注边界，此时有4个集合 {A}、{B}、{C}、{D}，当分界线的两侧都为 2 的时候进行合并。A和C所在的集合不是同一个集合，所以合并，原来的岛屿数量-1；同理，B和C所在集合不是同一个集合，所以合并，岛屿数量-1；B和D所在集合不是同一个集合，合并，岛屿数量-1；随后A和D已经在一个集合中了，所以不用再减了。最终，岛屿数量为1。

如果是一张地图，按照这种方式，想怎么切就怎么切，只需要记录每块的边界，然后进行合并。最终就能得到岛屿的数量。这种方案是并行的，甚至不需要加锁。