Comment on page
200.Number-of-Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
遍历graph寻找陆地“1”，以“1”为中心，使用DFS把四周变成“0”
Complexity Analysis
- Time complexity : O(_M×N) where M is the number of rows and _N is the number of columns.
- Space complexity : worst case O(_M×N) in case that the grid map is filled with lands where DFS goes by M×_N deep.
class Solution {
public int numIsLands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
if (grid[r][c] == '1') {
num_islands++;
dfs(grid, r, c);
}
}
}
return num_islands;
}
private void dfs(char[][] grid, int r, int c) {
int nr = grid.length;
int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
}
遍历graph寻找陆地“1”，以“1”为中心，使用BFS把四周变成“0”
mplexity Analysis
- Time complexity : O(_M×N) where M is the number of rows and _N is the number of columns.
- Space complexity : O(_min(M,N)) because in worst case where the grid is filled with lands, the size of queue can grow up to min(M,,_N).
class Solution {
public int numIsland(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
if (grid[r][c] == '1') {
num_islands++;
grid[r][c] = '0'; // mark as visited
Queue<Integer> neighbors = new LinkedList<>();
neighbors.add(r * nc + c);
while (!neighbors.isEmpty()) {
int id = neighbors.remove();
int row = id / nc;
int col = id % nc;
if ( row - 1 >= 0 && grid[row-1][col] == '1') {
neighbors.add((row - 1) * nc + col);
grid[row-1][col] = '0';
}
if (row + 1 < nr && grid[row+1][col] == '1') {
neighbors.add((row+1) * nc + col);
grid[row+1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col-1] == '1') {
neighbors.add(row * nc + col - 1);
grid[row][col - 1] = '0';
}
if (col + 1 < nc && grid[row][col+1] == '1') {
neighbors.add(row * nc + col + 1);
grid[row][col+1] = '0';
}
}
}
}
}
}
}
class Solution {
class UnionFind {
int count; // # of connected components
int[] parent;
int[] rank;
public UnionFind(char[][] grid) { // for problem 200
count = 0;
int m = grid.length;
int n = grid[0].length;
parent = new int[m * n];
rank = new int[m * n];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '1') {
parent[i * n + j] = i * n + j;
++count;
}
rank[i * n + j] = 0;
}
}
}
public int find(int i) { // path compression
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
}
public void union(int x, int y) { // union with rank
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
if (rank[rootx] > rank[rooty]) {
parent[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
parent[rootx] = rooty;
} else {
parent[rooty] = rootx;
rank[rootx] += 1;
}
--count;
}
}
public int getCount() {
return count;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int nr = grid.length;
int nc = grid[0].length;
int num_islands = 0;
UnionFind uf = new UnionFind(grid);
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') {
uf.union(r * nc + c, (r-1) * nc + c);
}
if (r + 1 < nr && grid[r+1][c] == '1') {
uf.union(r * nc + c, (r+1) * nc + c);
}
if (c - 1 >= 0 && grid[r][c-1] == '1') {
uf.union(r * nc + c, r * nc + c - 1);
}
if (c + 1 < nc && grid[r][c+1] == '1') {
uf.union(r * nc + c, r * nc + c + 1);
}
}
}
}
return uf.getCount();
}
}
Last modified 2yr ago