200 岛屿数量
题解中这里修改了原数组,大家如果面试的时候,要问清楚面试官是否能修改原数组,不能的话就得加入标记数组,不要一给题就直接上手
解法一: dfs
我的解法
class Solution {
private:
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& isVisited, int x,
int y) {
int n = grid.size();
int m = grid[0].size();
for (int i = 0; i < 4; i++) {
int a = x + dx[i];
int b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == '1' &&
!isVisited[a][b]) {
isVisited[a][b] = true;
dfs(grid, isVisited, a, b);
}
}
}
public:
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<bool>> isVisited(n, vector<bool>(m, false));
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1' && !isVisited[i][j]) {
ans++;
isVisited[i][j] = true;
dfs(grid, isVisited, i, j);
}
}
}
return ans;
}
};
复杂度分析
时间复杂度:O(MN),其中 M 和 N 分别为行数和列数。
空间复杂度:O(MN),在最坏情况下,整个网格均为陆地,深度优先搜索的深度达到 MN。
解法二: bfs
我的解法
与dfs类似
class Solution {
private:
typedef pair<int,int> PII;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& isVisited, int x, int y){
int n = grid.size();
int m = grid[0].size();
queue<PII> q;
q.push({x, y});
while(!q.empty()){
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i++){
int a = t.first + dx[i];
int b = t.second + dy[i];
if(a >= 0 && a < n && b >=0 && b < m && grid[a][b] == '1' && !isVisited[a][b]){
isVisited[a][b] = true;
q.push({a, b});
}
}
}
}
public:
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<bool>> isVisited(n, vector<bool>(m, false));
int ans = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == '1' && !isVisited[i][j]){
ans++;
bfs(grid, isVisited, i, j);
}
}
}
return ans;
}
};
复杂度分析
时间复杂度:O(MN),其中 M 和 N 分别为行数和列数。
空间复杂度:O(min(M,N)),在最坏情况下,整个网格均为陆地,队列的大小可以达到 min(M,N)。
解法三: 并查集
class Solution {
private:
vector<int> p;
vector<bool> isVisited;
int res;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int Find(int x) {
if (p[x] != x)
p[x] = Find(p[x]);
return p[x];
}
void Union(int x, int y) {
// 每次合并都要res减一,因此如果合并过直接跳过,以免res多减
if (Find(x) == Find(y))
return;
p[Find(x)] = Find(y);
res--;
}
public:
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
p.resize(n * m);
isVisited.resize(n * m);
res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int idx = i * m + j;
if (grid[i][j] == '1') {
p[idx] = idx;
res++;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int idx = i * m + j;
if (grid[i][j] == '1') {
// 只有这个地方需要标记已遍历
isVisited[idx] = true;
for (int k = 0; k < 4; k++) {
int a = i + dx[k];
int b = j + dy[k];
if (a >= 0 && a < n && b >= 0 && b < m &&
grid[a][b] == '1' && !isVisited[a * m + b]) {
// 这里不需要标记遍历,因为Union不会继续往下访问下一个节点
// 不是递归函数!
Union(idx, a * m + b);
}
}
}
}
}
return res;
}
};
复杂度分析
时间复杂度:O(MN×α(MN)),其中 M 和 N 分别为行数和列数。注意当使用路径压缩(见 find 函数)和按秩合并(见数组 rank)实现并查集时,单次操作的时间复杂度为 α(MN),其中 α(x) 为反阿克曼函数,当自变量 x 的值在人类可观测的范围内(宇宙中粒子的数量)时,函数 α(x) 的值不会超过 5,因此也可以看成是常数时间复杂度。
空间复杂度:O(MN),这是并查集需要使用的空间。
我没有使用按秩合并