73. 矩阵置零
描述
- 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
思路
- 时间复杂度O(mn),空间复杂度O(mn)的算法，复制一份Matrix，将0对应行列的元素置位0.
- 时间复杂度O(mn),空间复杂度O(m + n)的算法，利用一个M大小和一个N大小的数组，保存0元素的小标，然后将对应行列的元素置位0.
- 时间复杂度O(mn),空间复杂度O(1)的算法，利用首行首列的元素来表示该行该列是否有0元素，然后将对应行列的元素置位0.该方法需先统计首行首列自己是否有0元素，最后将首行首列置0.(参考)
Tips
- 题目需要遍历每个元素，所以时间复杂度O(mn)是较难优化的，突破点在于空间复杂度。
- 第一种解法直接复制了整个数组，仔细思考下其实只需保存0元素的小标即可，此时可将空间复杂度优化为O(m + n)
- 进一步优化，要将空间复杂度降为O(1),则需利用数组本身来保存0的位置了。不难想到可以将上述额外的两个数组转换为首行首列，具体步骤如下：
1)检查并记录第一行和第一列是否需要归零；
2)遍历矩阵，一旦发现某个元素为0，则将它所在的行和列的第一个元素置为0;
3)遍历第一行和第一列，如果是0，则将其对应的整个行或者整个列的元素置为0;
4)如果第一行或者第一列需要归零，则将其归零。时间复杂度为O(m*n)，空间复杂度为O(1)。
class Solution_73_01 {
public:
void setZeroes(vector<vector<int>>& matrix) {
vector<vector<int>> tmp = matrix;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[i].size(); ++j) {
if (tmp[i][j] == 0) {
for (int k = 0; k != matrix[i].size(); ++k) matrix[i][k] = 0;
for (int k = 0; k != matrix.size(); ++k) matrix[k][j] = 0;
}
}
}
}
};
class Solution_73_02 {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.empty()) return;
int hight = matrix.size(), width = matrix[0].size();
vector<bool> row0, col0;
row0.assign(hight, false);
col0.assign(width, false);
for (int i = 0; i < hight; ++i) { //记录0点的位置
for (int j = 0; j < width; ++j) {
if (matrix[i][j] == 0) {
row0[i] = true;
col0[j] = true;
}
}
}
for (int i = 0; i < row0.size(); ++i) {
if (!row0[i]) continue;
for (int j = 0; j < width; ++j) {
matrix[i][j] = 0;
}
}
for (int i = 0; i < col0.size(); ++i) {
if (!col0[i]) continue;
for (int j = 0; j < hight; ++j) {
matrix[j][i] = 0;
}
}
}
};
class Solution_73_03 {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.empty()) return;
int hight = matrix.size(), width = matrix[0].size();
bool isHasZeroRow = false, isHasZeroCol = false;
for (int i = 0; i < hight; ++i) {
if (matrix[i][0] == 0) {
isHasZeroRow = true;
break;
}
}
for (int i = 0; i < width; ++i) {
if (matrix[0][i] == 0) {
isHasZeroCol = true;
break;
}
}
// 将0元素所在行列的第一个元素置为0
for(int i = 1; i < hight; ++i){
for(int j = 1; j < width; ++j){
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 根据首行、首列将对应元素置0
for(int row = 1; row < hight; ++row){
if(matrix[row][0] == 0){
for(int col = 1; col < width; ++col){
matrix[row][col] = 0;
}
}
}
for(int col = 1; col < width; ++col){
if(matrix[0][col] == 0){
for(int row = 1; row < hight; ++row){
matrix[row][col] = 0;
}
}
}
cout<< isHasZeroRow << " " << isHasZeroCol << endl;
// 处理首行、首列
if(isHasZeroRow){
for(int i = 0; i < hight; ++i){
matrix[i][0] = 0;
}
}
if(isHasZeroCol){
for(int i = 0; i < width; ++i){
matrix[0][i] = 0;
}
}
}
};
