Leetcode 200. 岛屿数量 TLE

问题链接：https://leetcode.com/problems/number-of-islands/

给定一个由“1”（陆地）和“0”（水）组成的二维网格图，计算岛屿的数量。岛屿四面环水，相邻陆地水平或垂直连接而成。您可以假设网格的所有四个边缘都被水包围。

示例1：

Input:

11110
11010
11000
00000

输出：1

我的逻辑是简单地从每个节点进行 dfs 并跟踪连接的组件。 第 46 个测试用例超出了时间限制 (TLE)，有人可以帮助我优化此代码吗？

类解决方案（对象）：

def numIslands(self, grid):

    def in_grid(x, y):
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])

    def neighbours(node):
        p, q = node
        dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        return [(x, y) for x, y in [(p + i, q + j) for i, j in dir] if in_grid(x, y)]

    def dfs(node):
        visited.append(node)
        for v in neighbours(node):
            if grid[v[0]][v[1]]== "1" and v not in visited:
                dfs(v)

    components = 0
    visited = []
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            node = (i, j)
            if grid[i][j] == "1" and node not in visited:
                components += 1
                dfs(node)

    return components

我认为你的做法是正确的。然而你正在使用visited as a list这需要O(n)来搜索一个值。所以它的总体时间复杂度是O(N^2)。我建议使用set而不是list这是一个哈希表。

只需要修改两部分：

• visited = [] -> visited = set()
• visited.append(node) ->visited.add(node)

我确认已接受。现在node not in visited takes O(1)所以总体时间复杂度是O(N).

% 与大多数其他 LeetCode 问题一样，问题陈述不提供有关输入数据的任何信息。但由于您的代码是 TLE，所以我们可以假设我们无法以时间复杂度解决它O(n^2).