vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; int n = (int)matrix.size(), m = (int)matrix[0].size(), MAX_LEN = 10002; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (matrix[i][j] != 0) { int top = (i - 1 < 0) ? MAX_LEN : matrix[i-1][j]; int left = (j - 1 < 0) ? MAX_LEN : matrix[i][j-1]; matrix[i][j] = 1 + min(top, left); } } for (int i = n - 1; i >= 0; i--) { for (int j = m - 1; j >= 0; j--) { if(matrix[i][j] != 0) { int right = (j + 1 >= m) ? MAX_LEN: matrix[i][j+1]; int bottom = (i + 1 >= n) ? MAX_LEN: matrix[i+1][j]; matrix[i][j] = min(min(right, bottom) + 1, matrix[i][j]); } } } return matrix; }
时间复杂度 $o(n^2)$
空间复杂度 $o(1)$
1 2
Runtime: 184 ms, faster than 96.53% of C++ online submissions for 01 Matrix. Memory Usage: 20.9 MB, less than 91.39% of C++ online submissions for 01 Matrix.
有人问，为啥要两次遍历？ 不能像下面这么写吗？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
// 错误的写法 vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) { if (matrix.empty()) return {}; int n = (int)matrix.size(), m = (int)matrix[0].size(); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (matrix[i][j] != 0) { int top = (i - 1 < 0) ? INT32_MAX : matrix[i-1][j]; int left = (j - 1 < 0) ? INT32_MAX : matrix[i][j-1]; int right = (j + 1 >= m) ? INT32_MAX : matrix[i][j+1]; int bottom = (i + 1 >= n) ? INT32_MAX : matrix[i+1][j]; matrix[i][j] = 1 + min(min(top, left), min(right, bottom)); } } } return matrix; }
