30 计算岛屿的个数(Number of Islands)

30 计算岛屿的个数(Number of Islands),第1张

文章目录
    • 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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/756728.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-30
下一篇 2022-04-30

发表评论

登录后才能评论

评论列表(0条)

保存