Java "Number of Islands" 中的算法问题超出了时间限制

Question

对于 leetcode 200 岛的数量，这个解决方案工作正常。但是，对于较低的解决方案，由于超过时间限制而导致提交失败。以我的理解，两种解决方案都应该同时运行。你能帮忙吗？

class Solution {
    // BFS time O(mn) | space O(min(m,n))
    public int numIslands(char[][] grid) {
        int islandsCount = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    islandsCount++;
                    bfs(grid, i, j);
                }
            }
        }
        return islandsCount;
    }

    public static void bfs(char[][] grid, int row, int col) {
        int rc = grid.length;
        int cc = grid[0].length;
        Deque<Integer> queue = new ArrayDeque<Integer>();
        queue.offer(row*cc + col);
        while (!queue.isEmpty()) {
            Integer spotIdx = queue.poll();
            int i = spotIdx/cc, j = spotIdx%cc;
            // grid[i][j] = '0';
            if (i-1 >= 0 && grid[i-1][j] == '1') {
                queue.offer((i-1)*cc+j);
                grid[i-1][j] = '0';
            }
            if (i+1 < rc && grid[i+1][j] == '1') {
                queue.offer((i+1)*cc+j);
                grid[i+1][j] = '0';
            }
            if (j-1 >= 0 && grid[i][j-1] == '1') {
                queue.offer(i*cc+(j-1));
                grid[i][j-1] = '0';
            }
            if (j+1 < cc && grid[i][j+1] == '1') {
                queue.offer(i*cc+(j+1));
                grid[i][j+1] = '0';
            }
        }
        return;
    }
}

以下版本会抛出超时，但在某些测试用例中仍能给出正确答案。

class Solution {
    // BFS time O(mn) | space O(min(m,n))
    public int numIslands(char[][] grid) {
        int islandsCount = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    islandsCount++;
                    bfs(grid, i, j);
                }
            }
        }
        return islandsCount;
    }

    public static void bfs(char[][] grid, int row, int col) {
        int rc = grid.length;
        int cc = grid[0].length;
        Deque<Integer> queue = new ArrayDeque<Integer>();
        queue.offer(row*cc + col);
        while (!queue.isEmpty()) {
            Integer spotIdx = queue.poll();
            int i = spotIdx/cc, j = spotIdx%cc;
            grid[i][j] = '0';
            if (i-1 >= 0 && grid[i-1][j] == '1') {
                queue.offer((i-1)*cc+j);
            }
            if (i+1 < rc && grid[i+1][j] == '1') {
                queue.offer((i+1)*cc+j);
            }
            if (j-1 >= 0 && grid[i][j-1] == '1') {
                queue.offer(i*cc+(j-1));
            }
            if (j+1 < cc && grid[i][j+1] == '1') {
                queue.offer(i*cc+(j+1));
            }
        }
        return;
    }
}

Answer 1

看看这个特定的输入：

第一次调用 bfs 时，它得到 1 和 1 作为 i 和 j 的值。

队列收到它再次拉取的坐标 (1, 1)。

单元格被清除，所以我们得到：

那么四个if条件中有两个为真，队列接收坐标(2, 1)和(1, 2)。

在第二次迭代中，从队列中弹出 (2, 1)，并清除单元格：

只有一个 if 条件为真，并且 (2, 2) 正在推送到队列，队列现在有 (1, 2) 和 (2, 2)。

然后在第三次迭代中从队列中弹出 (1, 2)，并清除单元格：

一个if条件为真，将(2, 2)推入队列。但是现在队列中有两次 (2, 2)！

因此在第四次迭代中，(2, 2) 被弹出并清除：

没有if条件为真。

第五次迭代会再次pop (2, 2)，但是已经被清除处理过，所以这是一次无用的迭代。

这只是一个简单的示例，但在更大的网格中，队列中“重复”坐标的数量会迅速增加，并且它们都代表将发生的迭代……什么都没有。这是浪费时间。显然，测试服包括这样的情况，由于这种无用的开销，这会使你的函数运行超时。

您的代码的第一个版本不允许重复项进入队列。

Java "Number of Islands" 中的算法问题超出了时间限制

time limit exceeded for algorithm question in Java "Number of Islands"

java

algorithm

time-complexity

breadth-first-search