岛屿数量问题实现遇TLE：拆分函数是否为性能瓶颈？

我实现了LeetCode上的「岛屿数量」问题，代码能通过测试用例，但提交时出现超时（TLE）。我认为方案逻辑和官方解法一致，只是把代码拆成了多个函数减少重复，想请教是拆分函数导致的问题，还是有其他原因？

附上我的实现代码：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        from collections import deque
        
        queue = deque()
        islands = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # find the start of the island
                if grid[i][j] == "1":
                    islands += 1
                    queue.append((i, j))
                    self.destroyIsland(grid, queue)
        return islands
                    
    def destroyIsland(self, grid, queue):
        directions = ((0, -1), (0, 1), (-1, 0), (1, 0))
        while queue:
            curr_m, curr_n = queue.popleft()
            
            grid[curr_m][curr_n] = "0"
    
            for direction in directions:
                self.validateBounds(curr_m + direction[0], curr_n + direction[1], grid, queue)
        
    def validateBounds(self, m, n, grid, queue):
        if m >= 0 and n >= 0 and m < len(grid) and n < len(grid[0]) and grid[m][n] == "1":
            queue.append((m, n))

问题原因分析 #

拆分函数本身不会是超时的主要原因，你的代码核心问题是未在入队时标记已访问，导致大量重复入队，严重拖慢了BFS的效率：

• 官方BFS解法中，通常在将坐标加入队列的同时就把对应格子设为"0"（标记为已访问），避免后续其他相邻节点重复将其加入队列。
• 你的代码仅在从队列取出节点时才标记为"0"，而validateBounds只判断格子为"1"就直接入队。这会导致同一个坐标被多个相邻节点重复加入队列，队列中堆积大量重复元素，处理这些无效元素会额外消耗大量时间，在大规模测试用例下直接触发超时。

举个简单例子：某个"1"的上下左右都是"1"，这四个相邻节点都会把这个坐标加入队列，最终队列里会出现多个相同的坐标，后续处理时重复执行设为"0"的操作，完全是冗余开销。

修复方案 #

在validateBounds入队的同时就标记已访问，同时去掉destroyIsland中重复的标记操作：

class Solution:
    from collections import deque  # 移到类外，避免重复导入
    directions = ((0, -1), (0, 1), (-1, 0), (1, 0))  # 设为类属性，复用
    
    def numIslands(self, grid: List[List[str]]) -> int:
        queue = deque()
        islands = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    islands += 1
                    grid[i][j] = "0"  # 初始节点入队前先标记
                    queue.append((i, j))
                    self.destroyIsland(grid, queue)
        return islands
                    
    def destroyIsland(self, grid, queue):
        while queue:
            curr_m, curr_n = queue.popleft()
    
            for direction in self.directions:
                self.validateBounds(curr_m + direction[0], curr_n + direction[1], grid, queue)
        
    def validateBounds(self, m, n, grid, queue):
        if m >= 0 and n >= 0 and m < len(grid) and n < len(grid[0]) and grid[m][n] == "1":
            grid[m][n] = "0"  # 入队时立即标记已访问
            queue.append((m, n))

额外优化点 #

• 将from collections import deque移到类定义外，避免每次调用numIslands时重复导入模块。
• 把directions设为类属性，不用每次调用destroyIsland都重新创建元组，减少微小的性能损耗。

内容的提问来源于stack exchange，提问作者ayylamow