跳转至

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),这是并查集需要使用的空间。

我没有使用按秩合并