LeetCode 0073 - Set Matrix Zeroes
# Hints
- 思维
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given a matrix, if an element is , set its entire row and column to . Do it in-place.
Example 1:
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:
A straight forward solution using space is probably a bad idea.
A simple improvement uses space, but still not the best solution.
Could you devise a constant space solution?
# 题意
给定一个 的矩阵,如果 ,则将矩阵第 行的所有元素和第 行的所有元素置为 。要求使用 的额外空间解决问题。
# 题解
如果允许使用 的额外空间,问题非常简单,只需要分别用两个标记数组 和 分别记录第 行和第 列是否要置为 ,先遍历一次矩阵求出 和 数组,再遍历一次矩阵染色即可。
标解给出的方法是,借用原矩阵的空间求解。我们特殊处理原矩阵第 行和第 列,然后将这块空间用作标记数组即可。
细节问题:
- 注意特判空矩阵。
# AC代码
class Solution {
public:
void setZeroes(vector<vector<int>> & matrix) {
// 特判
if (matrix.empty()) {
return;
}
// 初始化
int m = matrix.size(), n = matrix.front().size();
// 预处理
bool column0 = false;
for (int i = 0; i < m; i ++) {
if (matrix[i][0] == 0) {
column0 = true;
break;
}
}
bool row0 = false;
for (int j = 0; j < n; j ++) {
if (matrix[0][j] == 0) {
row0 = true;
break;
}
}
for (int i = 1; i < m; i ++) for (int j = 1; j < n; j ++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
// 染色
for (int i = 1; i < m; i ++) for (int j = 1; j < n; j ++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
if (column0) for (int i = 0; i < m; i ++) {
matrix[i][0] = 0;
}
if (row0) for (int j = 0; j < n; j ++) {
matrix[0][j] = 0;
}
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01