Leetcode 417 Превышен лимит времени BFS
Я работаю над Leetcode 417 Pacific Atlantic Water Flow:
Есть прямоугольный остров
m x n, который граничит как с Тихим, так и с Атлантическим океаном. Тихий океан касается левого и верхнего края острова, а Атлантический океан касается правого и нижнего края острова.Остров разделен на сетку квадратных ячеек. Вам дана
m x nцелочисленная матрицаheights, гдеheights[r][c]представляет высоту над уровнем моря ячейки по координате(r, c).На острове выпадает много дождя, и дождевая вода может течь в соседние ячейки прямо на север, юг, восток и запад, если высота соседней ячейки меньше или равна высоте текущей ячейки. Вода может перетекать из любой клетки, прилегающей к океану, в океан.
Возвращает результат двумерного списка координат сетки, где
result[i] = [ri, ci]означает, что дождевая вода может течь из ячейки(ri, ci)как в Тихий, так и в Атлантический океаны.
Мое решение ниже. У меня возникает ошибка превышения лимита времени для очень большого тестового примера, например
[[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19],[72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,20],[71,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,90,21],[70,135,192,193,194,195,196,197,198,199,200,201,202,203,204,205,152,91,22], ...]
Я не могу понять, почему мой BFS не сработал в разумные сроки. Что мне не хватает?
class Solution:
def pacificAtlantic(self, heights):
rows, cols = len(heights), len(heights[0])
# define directions
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
def bfs(node, visited):
Q = [node]
while Q:
x, y = Q.pop(0)
visited[x][y] = True
for dx, dy in directions:
next_x, next_y = x + dx, y + dy
if next_x < 0 or next_x >= rows:
continue
if next_y < 0 or next_y >= cols:
continue
if visited[next_x][next_y]:
continue
if heights[x][y] > heights[next_x][next_y]:
continue
Q.append((next_x, next_y))
# pacific
pacific_start = [[0, i] for i in range(cols)] + [[i, 0] for i in range(1, rows)]
pacific_visited = [[False for _ in range(cols)] for _ in range(rows)]
for row, col in pacific_start:
if not pacific_visited[row][col]:
bfs((row, col), pacific_visited, 0)
# atlantic
atlantic_start = [[rows - 1, i] for i in range(cols)] + [[i, cols - 1] for i in range(0, rows - 1)]
atlantic_visited = [[False for _ in range(cols)] for _ in range(rows)]
for row, col in atlantic_start:
if not atlantic_visited[row][col]:
bfs((row, col), atlantic_visited, 0)
# find the common land
ans = []
for i in range(rows):
for j in range(cols):
if pacific_visited[i][j] and atlantic_visited[i][j]:
ans.append((i, j))
return ans
Ответы 2
В вашей функции bfs есть две проблемы, которые негативно влияют на производительность:
pop(0)не эффективен наlist. Вместо этого используйтеdeque- Вы помечаете узел как посещенный после того, как взяли его из очереди, но это означает, что вы можете иметь несколько копий одной и той же ячейки в очереди, увеличивая количество итераций, которые сделает цикл BFS. Вместо этого пометьте узел как посещенный в момент помещения его в очередь.
Вот код вашей функции bfs с минимальными изменениями, необходимыми для решения этих двух проблем:
def bfs(node, visited, test):
visited[node[0]][node[1]] = True # mark node when it enters the queue
Q = deque([node]) # Use a deque, not a list
while Q:
x, y = Q.popleft() # now it's an efficient operation
for dx, dy in directions:
next_x, next_y = x + dx, y + dy
if next_x < 0 or next_x >= rows:
continue
if next_y < 0 or next_y >= cols:
continue
if visited[next_x][next_y]:
continue
if heights[x][y] > heights[next_x][next_y]:
continue
visited[next_x][next_y] = True # mark node when it enters the queue
Q.append((next_x, next_y))
@JohnGordon, не так эффективно, как у dequepopleft. Цитата из документации : «Хотя объекты list поддерживают аналогичные операции, они оптимизированы для быстрых операций фиксированной длины и требуют затрат на перемещение памяти O(𝑛) для операций pop(0) и insert(0, v), которые изменяют как размер, так и положение базовых данных. представление."
@JohnGordon Ожидаете ли вы, что это будет постоянное время?
Вы также можете использовать set() и упростить условия:
class Solution:
def pacificAtlantic(self, heights):
if not heights:
return []
rows, cols = len(heights), len(heights[0])
pacific = set([(row, 0) for row in range(rows)] + [(0, col) for col in range(1, cols)])
atlantic = set([(row, cols - 1) for row in range(rows)] + [(rows - 1, col) for col in range(cols - 1)])
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
def bfs(ocean):
Q = collections.deque(ocean)
while Q:
x, y = Q.popleft()
for dx, dy in directions:
if 0 <= dx + x < rows and 0 <= dy + y < cols and (dx + x, dy + y) not in ocean and heights[dx + x][dy + y] >= heights[x][y]:
Q.append((dx + x, dy + y))
ocean.add((dx + x, dy + y))
return ocean
return tuple(bfs(pacific) & bfs(atlantic))
pop(0) действительно неэффективен в списке?