【LeetCode】25. 542_01 Matrix · 01矩阵

心已赠人 2024-04-01 13:20 93阅读 0赞

## 题目描述 ##

#### 英文版描述 ####

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

#### 英文版地址 ####

https://leetcode.com/problems/01-matrix/

#### 中文版描述 ####

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

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

示例 1：

![56ca644f9812dc4813a30df49a9553b8.png][]

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

示例 2：

![88dad0e7cac49893fe28d5aef94a3be6.png][]

输入：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

#### 中文版地址 ####

https://leetcode.cn/problems/01-matrix/

## 解题思路 ##

距离最近，即求（行差+列差）的最小值，典型的求最短距离问题，可以考虑广度优先算法

## 解题方法 ##

### 俺这版 ###

不出意外，俺超时叻=\[,,\_,,\]:3

![85a07cf72821b44139982c72f94f7d8a.png][]

class Solution {
         class Point {
            int value;
            int i;
            int k;
        }
    
        public int[][] updateMatrix(int[][] mat) {
     Deque<Point> deque = new LinkedList<>();
            // add all to deque
            int[][] re = mat;
            for (int i = 0; i < mat.length; i++) {
                for (int k = 0; k < mat[0].length; k++) {
                    // determine == 0 or not
                    if (mat[i][k] == 0) {
                        re[i][k] = 0;
                    } else {
                        Point center = new Point();
                        center.value = mat[i][k];
                        center.i = i;
                        center.k = k;
                        Point point = getDistance(deque, mat, center);
                        if (point != null) {
                            re[i][k] = Math.abs(point.i - i) + Math.abs(point.k - k);
                        }
                        deque.clear();
                    }
                }
            }
            return re;
        }
    
        private Point getDistance(Deque<Point> deque, int[][] mat, Point center) {
    
            if ((center.i + 1) < mat.length) {
                Point point = new Point();
                point.value = mat[center.i + 1][center.k];
                point.i = center.i + 1;
                point.k = center.k;
                deque.add(point);
            }
    
            if ((center.k + 1) < mat[0].length) {
                Point point = new Point();
                point.value = mat[center.i][center.k + 1];
                point.i = center.i;
                point.k = center.k + 1;
                deque.add(point);
            }
    
            if ((center.i - 1) >= 0) {
                Point point = new Point();
                point.value = mat[center.i - 1][center.k];
                point.i = center.i - 1;
                point.k = center.k;
                deque.add(point);
            }
            if ((center.k - 1) >= 0) {
                Point point = new Point();
                point.value = mat[center.i][center.k - 1];
                point.i = center.i;
                point.k = center.k - 1;
                deque.add(point);
            }
    
            while (!deque.isEmpty()) {
                Point peek = deque.pop();
                if (peek.value == 0) {
                    return peek;
                } else {
                    return getDistance(deque, mat, peek);
                }
            }
            return null;
        }
    }

### 官方版 ###

#### **广度优先搜索** ####

![991a8679e2d67415bf18062693a67e36.png][]

class Solution {
        public int[][] updateMatrix(int[][] matrix) {
            // 首先将 0 边上的 1 入队
            int[] dx = new int[] {-1, 1, 0, 0};
            int[] dy = new int[] {0, 0, -1, 1};
            Queue<int[]> queue = new LinkedList<>();
            int m = matrix.length, n = matrix[0].length;
            int[][] res = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        for (int k = 0; k < 4; k++) {
                            int x = i + dx[k];
                            int y = j + dy[k];
                            if (x >= 0 && x < m && y >= 0 && y < n 
                                    && matrix[x][y] == 1 && res[x][y] == 0) {
                                // 这是在 0 边上的1。需要加上 res[x][y] == 0 的判断防止重复入队
                                res[x][y] = 1;
                                queue.offer(new int[] {x, y});
                            }
                        }
                    }
                }
            }
    
            while (!queue.isEmpty()) {
                int[] point = queue.poll();
                int x = point[0], y = point[1];
                for (int i = 0; i < 4; i++) {
                    int newX = x + dx[i];
                    int newY = y + dy[i];
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n 
                            && matrix[newX][newY] == 1 && res[newX][newY] == 0) {
                        res[newX][newY] = res[x][y] + 1;
                        queue.offer(new int[] {newX, newY});
                    }
                }
            }
            return res;
        }
    }

**复杂度分析**

*  时间复杂度：O(mn)，其中 m 为矩阵行数，n 为矩阵列数，即矩阵元素个数。广度优先搜索中每个位置最多只会被加入队列一次，因此只需要 O(mn) 的时间复杂度。
 *  空间复杂度：O(mn)，其中 m 为矩阵行数，n为矩阵列数，即矩阵元素个数。除答案数组外，最坏情况下矩阵里所有元素都为 0，全部被加入队列中，此时需要 O(mn) 的空间复杂度。

#### 动态规划 ####

![23654cecfb9a0bdcea9fddf5a41519a6.png][]

class Solution {
        static int[][] dirs = {
       {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
        public int[][] updateMatrix(int[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            // 初始化动态规划的数组，所有的距离值都设置为一个很大的数
            int[][] dist = new int[m][n];
            for (int i = 0; i < m; ++i) {
                Arrays.fill(dist[i], Integer.MAX_VALUE / 2);
            }
            // 如果 (i, j) 的元素为 0，那么距离为 0
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (matrix[i][j] == 0) {
                        dist[i][j] = 0;
                    }
                }
            }
            // 只有 水平向左移动 和 竖直向上移动，注意动态规划的计算顺序
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                    }
                    if (j - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
            }
            // 只有 水平向左移动 和 竖直向下移动，注意动态规划的计算顺序
            for (int i = m - 1; i >= 0; --i) {
                for (int j = 0; j < n; ++j) {
                    if (i + 1 < m) {
                        dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                    }
                    if (j - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j - 1] + 1);
                    }
                }
            }
            // 只有 水平向右移动 和 竖直向上移动，注意动态规划的计算顺序
            for (int i = 0; i < m; ++i) {
                for (int j = n - 1; j >= 0; --j) {
                    if (i - 1 >= 0) {
                        dist[i][j] = Math.min(dist[i][j], dist[i - 1][j] + 1);
                    }
                    if (j + 1 < n) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                    }
                }
            }
            // 只有 水平向右移动 和 竖直向下移动，注意动态规划的计算顺序
            for (int i = m - 1; i >= 0; --i) {
                for (int j = n - 1; j >= 0; --j) {
                    if (i + 1 < m) {
                        dist[i][j] = Math.min(dist[i][j], dist[i + 1][j] + 1);
                    }
                    if (j + 1 < n) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][j + 1] + 1);
                    }
                }
            }
            return dist;
        }
    }

**复杂度分析**

*  时间复杂度：O(mn)，其中 m 为矩阵行数，nn 为矩阵列数。计算dist 数组的过程中我们需要遍历四次矩阵，因此时间复杂度为 O(4mn)=O(4mn)=O(mn)。
 *  空间复杂度：O(1)，这里我们只计算额外的空间复杂度。除了答案数组以外，我们只需要常数空间存放若干变量

## 总结 ##

看了答案后，背着答案写了一版，不超时了(╥﹏╥)

![6f8408e108f1722df99de41648cf1f18.png][]

[56ca644f9812dc4813a30df49a9553b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f24ee65175d144cab0c93abd69ad26d0.png
[88dad0e7cac49893fe28d5aef94a3be6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/4fa23f9545b144978c816c3a8da66dbf.png
[85a07cf72821b44139982c72f94f7d8a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a10278e15c744e4e96e1ca30eda4a788.png
[991a8679e2d67415bf18062693a67e36.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/c892e5f492284a0483434ef467b10015.png
[23654cecfb9a0bdcea9fddf5a41519a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/65a48522bf704da986b0871044bd3149.png
[6f8408e108f1722df99de41648cf1f18.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9a5aff1742b54882955f309bc476ce5e.png