题目描述

[EN | CN]

给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。

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

示例 1:

1
2
3
4
5
6
7
8
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0

示例 2:

1
2
3
4
5
6
7
8
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1

注意:

  • 给定矩阵的元素个数不超过 10000。
  • 给定矩阵中至少有一个元素是 0。
  • 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解法 1:BFS

比较直接的做法,我们从已经知道的最小距离(即值等于 0 的元素)开始,逐渐往外扩散。维护一个 next_pos 队列来保存已经计算出距离、但还没计算邻居距离的元素,然后不断从该队列取元素,计算其邻居的距离,如果超出矩阵范围或者已经计算过了则跳过,否则等于当前元素的距离加一。

假设矩阵的维度为 $m \times n$,那么

  • 时间复杂度为 $O(mn)$,与元素数量相同;
  • 空间复杂度为 $O(mn)$,保存结果。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        num_row, num_column = len(matrix), len(matrix[0])
        dist = [[-1 for _ in range(num_column)] for _ in range(num_row)]

        next_pos = []
        for i in range(num_row):
            for j in range(num_column):
                if matrix[i][j] == 0:
                    dist[i][j] = 0
                    next_pos.append((i, j))

        while next_pos:
            i, j = next_pos.pop(0)
            for next_i, next_j in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if 0 <= next_i < num_row and  0 <= next_j < num_column and dist[next_i][next_j] == -1:
                    dist[next_i][next_j] = dist[i][j] + 1
                    next_pos.append((next_i, next_j))

        return dist
  • 执行用时:836 ms,在所有 Python3 提交中击败了 60.78% 的用户。
  • 内存消耗:16.7 MB,在所有 Python3 提交中击败了 100.00% 的用户。

解法 2:动规

这里我们考虑动规,对于某一个元素,它距离 0 的最小距离可能有几种情况:

  • 本身是 0,所以距离为 0;
  • 本身不是 0,距离为上下左右四个元素的最小距离 + 1。

所以这里我们考虑动规,考虑它的上下左右四个方向。但是每一步都要依赖上一步,并且我们有两个维度(水平、竖直)、每个维度两个方向(左右、上下),我们思考从哪里开始?

其实很简单,因为有每个维度只有两个方向,所以我们只需要两次动规即可:

  • 第一次动规只考虑当前元素的左上方元素,距离为左、上的元素的最小距离 + 1;
  • 第二次动规只考虑当前元素的右下方元素,距离为右、上的元素的最小距离 + 1。

通过这样两次动规,我们可以算出每个元素距离上下左右所有方向的 0 的最小距离。

假设矩阵的维度为 $m \times n$,那么

  • 时间复杂度为 $O(mn)$,与元素数量相同;
  • 空间复杂度为 $O(mn)$,保存结果,如果允许 inplace 修改矩阵的话,其实 $O(1)$ 就可以了。

实现与结果如下:

 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
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        num_row, num_column = len(matrix), len(matrix[0])
        max_dist = num_row * num_column
        dist = [
            [
                0 if matrix[i][j] == 0 else max_dist
                for j in range(num_column)
            ]
            for i in range(num_row)
        ]

        # First DP: top-to-bottom, left-to-right
        for i in range(num_row):
            for j in range(num_column):
                if i - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
                if j - 1 >= 0:
                    dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)

        # Second DP: bottom-to-top, right-to-left
        for i in range(num_row - 1, -1, -1):
            for j in range(num_column - 1, -1, -1):
                if i + 1 <= num_row - 1:
                    dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
                if j + 1 <= num_column - 1:
                    dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)

        return dist
  • 执行用时:764 ms,在所有 Python3 提交中击败了 77.55% 的用户。
  • 内存消耗:16.7 MB,在所有 Python3 提交中击败了 100.00% 的用户。
▲