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

题目描述

英文版描述

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：

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

中文版地址

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

解题思路

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

解题方法

俺这版

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

class Solution {
     class Point {
        int value;
        int i;
        int k;
    }
 
    public int[][] updateMatrix(int[][] mat) {
 Deque 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 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;
    }
}

官方版

广度优先搜索

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) 的空间复杂度。

动态规划

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)，这里我们只计算额外的空间复杂度。除了答案数组以外，我们只需要常数空间存放若干变量

总结

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

class Solution {
     class Point {
        int value;
        int i;
        int k;
    }
 
    public int[][] updateMatrix(int[][] mat) {
        Deque 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) {
                    Point center = new Point();
                    center.value = 0;
                    center.i = i;
                    center.k = k;
                    deque.offer(center);
                } else {
                    mat[i][k] = -1;
                }
            }
        }
        int[] dx = {-1, 0, 0, 1};
        int[] dy = {0, -1, 1, 0};
        while (!deque.isEmpty()) {
            Point pop = deque.pop();
            for (int i = 0; i < 4; i++) {
                Point point = new Point();
                point.value = pop.value + 1;
                point.i = pop.i + dx[i];
                point.k = pop.k + dy[i];
                if (point.i >= 0 && point.i < mat.length && point.k >= 0 && point.k < mat[0].length
                        && mat[point.i][point.k] == -1) {
                    mat[point.i][point.k] = pop.value + 1;
                    deque.offer(point);
                }
            }
        }
        return mat;
    }
}