30 计算岛屿的个数（Number of Islands）

文章目录

• • 1 题目
  • 2 解决方案
  • • 2.1 思路
    • 2.2 时间复杂度
    • 2.3 空间复杂度
  • 3 源码

1 题目

题目：计算岛屿的个数（Number of Islands）
描述：给一个 01 矩阵，求不同的岛屿的个数。0 代表海，1 代表岛，如果两个 1 相邻，那么这两个 1 属于同一个岛。我们只考虑上下左右为相邻。

lintcode题号——433，难度——easy

样例1：

输入：
[
  [1,1,0,0,0],
  [0,1,0,0,1],
  [0,0,0,1,1],
  [0,0,0,0,0],
  [0,0,0,0,1]
]
输出：
3

样例2：

输入：
[
  [1,1]
]
输出：
1

2 解决方案 2.1 思路

  通过遍历找到岛屿的边缘，然后用宽度优先搜索可以找到整个岛屿并将岛屿转变为海洋（即灌水法），岛屿计数+1，继续向后搜索岛屿直到整个区域搜索完成。

2.2 时间复杂度

  图上的宽度优先搜索，算法的时间复杂度为O(n+m)，其中n为节点数，m为边数。R行C列的矩阵，可以看成有R*C个节点和R*C*2条边的图，在其上进行BFS，时间复杂度为O(R*C)。

因为在图中的m的数量级最高是n的平方，所以也可以认为是O(m)，矩阵边数R*C*2，时间复杂度为O(R*C*2) = O(R*C)。

2.3 空间复杂度

  图上的宽度优先搜索，使用了queue队列数据结构，队列最大容量为节点数，即R*C，算法的空间复杂度为O(R*C)。

3 源码

细节：

1. 使用宽度优先搜索对岛屿进行灌水；
2. 在BFS中使用自定义数组和for循环来找到邻居；
3. 在BFS节点入队时就灌水，防止节点被重复搜索。

C++版本：

/**
* @param grid: a boolean 2D matrix
* @return: an integer
*/
int numIslands(vector> &grid) {
    // write your code here
    int result = 0;
    if (grid.empty() || grid.front().empty())
    {
        return result;
    }

    // 遍历整个区域
    for (int row = 0; row < grid.size(); row++)
    {
        for (int col = 0; col < grid.front().size(); col++)
        {
            if (grid.at(row).at(col) == true)
            {
                result++;
                bfs(grid, row, col); // 灌水法，将岛屿变为水
            }
        }
    }

    return result;
}

void bfs(vector> &grid, int row, int col)
{
    int r[] = {-1, 0, 1, 0};
    int c[] = {0, -1, 0, 1};

    queue> nodeQueue;
    nodeQueue.push(pair({row, col}));
    while (!nodeQueue.empty())
    {
        pair cur = nodeQueue.front();
        nodeQueue.pop();
        //grid.at(cur.first).at(cur.second) = false; // 不能d出队列才灌水，会导致节点被重复搜索
        for (int direction = 0; direction < 4; direction++)
        {
            int newRow = cur.first + r[direction];
            int newCol = cur.second + c[direction];
            if (isValid(grid, newRow, newCol) && grid.at(newRow).at(newCol) == true)
            {
                pair temp = make_pair(newRow, newCol);
                nodeQueue.push(temp);
                grid.at(newRow).at(newCol) = false; // 必须在进入队列时就灌水
            }
        }
    }
}

// 检测是否超出边界
bool isValid(vector> &grid, int row, int col)
{
    int maxRow = grid.size() - 1;
    int maxCol = grid.front().size() - 1;
    if (row < 0 || maxRow < row)
    {
        return false;
    }
    if (col < 0 || maxCol < col)
    {
        return false;
    }

    return true;
}