Leetcode200.岛屿数目TLE [英] Leetcode 200. Number of Islands TLE

问题描述

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

给出一张二维地图，分别是"1"(土地)和"0"(水)，计算岛屿的数量.一个岛屿被水包围，是通过水平或垂直连接相邻的土地而形成的.您可能会假设网格的所有四个边缘都被水包围了.

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.

示例1:

输入:

11110
11010
11000
00000

输出:1

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

My logic is to simply do dfs from every node and keep track of the connected components. Am getting Time Limit Exceeded (TLE) for the 46th test case, can someone help me optimize this code?

类解决方案(对象):

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 作为 list ，它需要 O(n)来搜索值.因此，它的总体时间复杂度为 O(N ^ 2).我建议使用 set ，而不要使用作为哈希表的 list .

I think your approach is correct. However you are using visited as a list which takes O(n) to search a value. So its overall time complexity is O(N^2). I would suggest to use set rather than list which is a hash table.

只有两部分需要修改:

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

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

我确认已接受.现在，未访问的节点占用 O(1)，因此总体时间复杂度为 O(N).

I confirmed that it is accepted. Now node not in visited takes O(1) so the overall time complexity is O(N).

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

% Like most of other LeetCode problems, the problem statement does not give any information about input data. But as your code is TLE so we can assume that we cannot solve it with time complexity O(n^2).

这篇关于Leetcode200.岛屿数目TLE的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！