算法-广度优先搜索-09

力扣-真题-岛屿数量

我的想法是 初始化一个 sum代表岛屿数量，
没遍历到一个 1, sum = sum + 1
然后从这个位置开始 进行广度优先搜索 把所有相连的1 全部变成0 （原地修改）。 然后再继续向下遍历 。
就能得到所有岛屿数量了。

publicintnumIslands(char[][]grid){intsum=0;for(inti=0;i<grid.length;i++){for(intj=0;j<grid[0].length;j++){if(grid[i][j]=='0')continue;sum++;bfs(grid,i,j);}}returnsum;}publicvoidbfs(char[][]grid,inti,intj){//边界情况if(i>=grid.length||j>=grid[0].length||i==-1||j==-1||grid[i][j]=='0')return;grid[i][j]='0';//四个方向进行遍历bfs(grid,i,j+1);bfs(grid,i+1,j);bfs(grid,i-1,j);bfs(grid,i,j-1);}

嗯， 今天开始加一个环节

复杂度分析

首先空间复杂度 是 O(1) , 因为是原地修改 没有额外的存储空间浪费。
然后时间复杂度计算
咱们拆成几个部分， 首先

• 第一个部分 肯定就是 两层 for循环遍历
  总共需要遍历 数组的数量m × 单个数组的元素数量n 此
  即 时间复杂度 在这一部分是 O(m×n)
• 第二部分 也就是最后的一部分就是BFS 遍历
  这一部分的分析 可以这样
  如果 这个 节点是grid[x][y] = ‘0’ 啥也不用处理 O(1)
  如果 这个节点 是 grid[x][y] = ‘1’ 那个 除了 grid[x][y]置为 ‘1’外
  主要就是找相邻的‘1’置为 ‘0’ ， 其实某种程度上来说， 你把其他节点 的 ‘1’ 置为 ‘0’ ，不就是帮其他节点做事吗 ， 平摊下来 最多 每一个节点都把‘1’置为 ‘0’ ， 也就是 在遍历 m× n的时候 顺便加一步 ‘1’置为 ‘0’ 以及 如果是 ‘0’ 跳过的判断， 这个时间复杂度 实际上是 O(1)
  当然啦， 最坏的情况下， grid[0][0】开始 bfs 会直接遍历整个图， 也就是m×n的复杂度。
  所以实际上 BFS的时间复杂度也是O(m×n)

但是这两部分的时间复杂度是分开的，互不影响，总体的时间复杂度就是O(m×n + m×n ）= 2O(m×n)
常数因子忽略， 所以最终的时间复杂度就是O(m×n)