我正在解决关于LeetCode的问题:
给定矩阵由0和1组成,找到每个单元格最近的0的距离。两个相邻单元之间的距离为1(重要点)。 如果输入:
[[0,0,0],
[0,1,0],
[1,1,1]]
然后输出:
[[0,0,0],
[0,1,0],
[1,2,1]]
我编写的代码将所有0
s的位置添加到队列中,并从队列中的每个这样的位置执行BFS。不幸的是它超时了。
给出的高度赞成的解决方案是这样的:
public class Solution {
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
queue.offer(new int[] {i, j});
}
else {
matrix[i][j] = Integer.MAX_VALUE;
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int r = cell[0] + d[0];
int c = cell[1] + d[1];
if (r < 0 || r >= m || c < 0 || c >= n ||
matrix[r][c] <= matrix[cell[0]][cell[1]] + 1) continue;
queue.add(new int[] {r, c});
matrix[r][c] = matrix[cell[0]][cell[1]] + 1;
}
}
return matrix;
}
}
虽然我或多或少了解它是如何工作的,但我有以下问题:
为什么我们必须检查matrix[r][c] <= matrix[cell[0]][cell[1]] + 1
- BFS是否保证如果边缘成本相等,那么它找到的特定节点的路径是最短的?为什么我们要检查呢?
无法保证BFS算法只能到达一次matrix[r][c]
。事实上,在这个问题上,它将达到多次。你所谈论的保证只有在第一次达到matrix[r][c]
时才有效。
因此,另一种解决方案是保留另一个Boolean
值矩阵,标记每个单元格是否已被访问过,并用!visited[r][c]
替换您提到的检查。但是,保留额外的矩阵需要额外的内存 - 这是偏好当前方法的原因。
执行此检查以确保在不能提供更好结果时不继续处理路径。
您的BFS解决方案很好,但效率不高。通过提前中止,您可以确保不执行无用操作,因此不会超时。
在Nlog(N)中也可以很容易地解决这个问题,其中N是矩阵中的单元总数,使用Dijkstra算法。 您需要做的唯一更改是,而不是一个目的地,您将所有0都视为目的地。 因此,所有0的初始距离将为零。然后你可以简单地继续Dijkstra。 更新:您发布的解决方案更好,因为其时间复杂度为O(N)。