当前位置：首页 > article >正文

LeetCode题练习与总结：01 矩阵--542

article 2025/1/15 17:37:32

一、题目描述

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 10^4
1 <= m * n <= 10^4
mat[i][j] is either 0 or 1.
mat 中至少有一个 0

二、解题思路

这个问题可以通过多源广度优先搜索（BFS）来解决。解题思路如下：

创建一个队列，用于存放所有的0的位置，这些位置是起点。
从这些起点开始，进行层序遍历，每一层的遍历都是距离起点的距离加1。
对于每个遍历到的1，更新其距离为当前层的距离。
遍历完成后，返回更新后的矩阵。

三、具体代码

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        
        // 初始化队列，将所有的0的位置加入队列
        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});
                } else {
                    // 将1的位置初始化为最大值，表示尚未访问
                    mat[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        
        // 开始层序遍历
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            
            // 遍历四个方向
            for (int[] direction : directions) {
                int newX = x + direction[0];
                int newY = y + direction[1];
                
                // 检查新位置是否在矩阵范围内，并且新位置的值可以更新
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && mat[newX][newY] > mat[x][y] + 1) {
                    mat[newX][newY] = mat[x][y] + 1;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
        
        return mat;
    }
}

这段代码首先将所有的0的位置加入队列，并将所有的1的位置设置为Integer.MAX_VALUE。然后，从队列中取出元素，遍历其四个方向，如果新位置在矩阵范围内并且新位置的值可以更新（即比当前值大），则更新新位置的值，并将其加入队列。最终，队列为空时，所有位置的距离都已经被正确更新。

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化队列时，我们需要遍历整个矩阵，这个步骤的时间复杂度是 O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。
在层序遍历过程中，每个元素最多只会被加入队列一次，因此队列中的元素数量最多是 m * n。每次从队列中取出一个元素，并对其四个方向进行遍历，这一步的时间复杂度是 O(4)，因为每个元素最多有四个相邻元素。
因此，层序遍历的总时间复杂度是 O(m * n)，因为每个元素都会被处理一次。

综上所述，总的时间复杂度是 O(m * n) + O(m * n) = O(m * n)。

2. 空间复杂度

队列的大小取决于矩阵中0的个数，在最坏的情况下，如果矩阵全为0，则队列的大小将是 m * n。
我们使用了额外的 directions 数组来表示四个方向，这个数组的大小是常数，因此它对空间复杂度的影响是 O(1)。
我们在原矩阵上进行更新，没有使用额外的矩阵来存储结果，因此除了队列之外，没有使用额外的空间。

综上所述，总的空间复杂度是 O(m * n)，这是在最坏情况下队列的最大空间需求。

五、总结知识点

类定义：class Solution 定义了一个名为 Solution 的类。
成员方法：public int[][] updateMatrix(int[][] mat) 定义了一个公共方法，该方法接收一个二维整数数组 mat 作为参数，并返回一个同样类型的数组。
二维数组：int[][] mat 是一个二维整数数组，用于表示给定的矩阵。
队列的使用：Queue<int[]> queue = new LinkedList<>(); 创建了一个队列，用于在广度优先搜索（BFS）中存储待处理的元素。
数组的初始化：int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 初始化了一个二维数组，表示四个可能的移动方向（右、左、下、上）。
嵌套循环：两个嵌套的 for 循环用于遍历矩阵的每个元素。
条件语句：if 语句用于检查矩阵中的元素是否为0，以及更新矩阵中的元素值。
队列操作：queue.offer(new int[]{i, j}); 将元素加入队列，queue.poll(); 从队列中取出元素。
边界检查：if (newX >= 0 && newX < m && newY >= 0 && newY < n) 用于确保新的坐标在矩阵的边界内。
矩阵更新：mat[newX][newY] = mat[x][y] + 1; 更新矩阵中元素的距离值。
常量：Integer.MAX_VALUE 是一个整型常量，表示整型可以表示的最大值，用于初始化矩阵中的1的位置。
广度优先搜索（BFS）：整个方法的核心是使用BFS算法来计算每个元素到最近的0的距离。
返回值：return mat; 返回更新后的矩阵。