05 August 2008
01矩阵中，返回每个元素距离最近的0的距离
BFS，如果从每个元素出发BFS，找到最近的0, 把0存入queue，然后从每个0开始，BFS扩散去找每个元素，更新哪个0最近。
时间复杂度O(m * n)，因为matrix的行 * 列, 空间复杂度同样为O(m * n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length;
// 0. 用一个额外的的矩阵来记录离最近的0的距离
int[][] dist = new int[m][n];
// 1. 将每个额外的矩阵的距离初始化为最大
for (int i = 0; i < m; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
// 2. 先遍历一遍最初的二维数组，遇到0，就将其对应的坐标存入到queue中，并更新额外矩阵的距离
Queue<int[]> queue = new ArrayDeque<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 0) {
queue.offer(new int[]{i, j});
dist[i][j] = 0;
}
}
}
int[][] dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
// 3. 从queue中，取出每个0所在的坐标进行BFS
while(!queue.isEmpty()) {
int[] cell = queue.poll();
int row = cell[0], col = cell[1];
for (int[] dir : dirs) {
int newRow = dir[0] + row;
int newCol = dir[1] + col;
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
if (dist[newRow][newCol] > dist[row][col] + 1) { // BFS扩散过程中+1，与邻近对比
dist[newRow][newCol] = dist[row][col] + 1;
queue.offer(new int[]{newRow, newCol}); //当前值改变后，继续BFS
}
}
}
}
return dist;
}
}
扫描两遍，根据第二次遍历的顺序，从下/右或上/左两个元素的距离来计算自己的最小距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[][] updateMatrix(int[][] matrix) {
int row = matrix.length, col = matrix[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] == 1) {
matrix[i][j] = Integer.MAX_VALUE;
if (i - 1 >= 0 && matrix[i - 1][j] != Integer.MAX_VALUE)
matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i - 1][j]);
if (j - 1 >= 0 && matrix[i][j - 1] != Integer.MAX_VALUE)
matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i][j - 1]);
}
}
}
for (int i = row - 1; i >= 0; i--) {
for (int j = col - 1; j >= 0; j--) {
if (i + 1 < row && matrix[i + 1][j] != Integer.MAX_VALUE)
matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i + 1][j]);
if (j + 1 < col && matrix[i][j + 1] != Integer.MAX_VALUE)
matrix[i][j] = Math.min(matrix[i][j], 1 + matrix[i][j + 1]);
}
}
return matrix;
}
DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int[][] updateMatrix(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) {
return matrix;
}
int range = matrix.length * matrix[0].length;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] != 0) {
int upCell = (i > 0) ? matrix[i - 1][j] : range;
int leftCell = (j > 0) ? matrix[i][j - 1] : range;
matrix[i][j] = Math.min(upCell, leftCell) + 1;
}
}
}
for (int i = matrix.length - 1; i >= 0; i--) {
for (int j = matrix[0].length - 1; j >= 0; j--) {
if (matrix[i][j] != 0) {
int downCell = (i < matrix.length - 1) ? matrix[i + 1][j] : range;
int rightCell = (j < matrix[0].length - 1) ? matrix[i][j + 1] : range;
matrix[i][j] = Math.min(Math.min(downCell, rightCell) + 1, matrix[i][j]);
}
}
}
return matrix;
}
}