# 73. Set Matrix Zeroes 矩阵置零

@TOC

## # 题目描述

Given a `m x n` matrix, if an element is 0, set its entire row and column to 0. 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]
]
``````

1. A straight forward solution using O(mn) space is probably a bad idea.
2. A simple improvement uses O(m + n) space, but still not the best solution.
3. Could you devise a constant space solution?

## # 解题方法

### # 原地操作

``````class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
M, N = len(matrix), len(matrix[0])
# (old + new)
if matrix and matrix[0]:
for m in range(M):
for n in range(N):
matrix[m][n] = (matrix[m][n] << 1) + (1 if matrix[m][n] else 0)
for m in range(M):
for n in range(N):
if self.getPos(matrix, m, n) == 0:
matrix[m][n] = matrix[m][n] >> 1 << 1
for m in range(M):
for n in range(N):
if matrix[m][n] & 1 == 0:
matrix[m][n] = 0
else:
matrix[m][n] >>= 1

def getPos(self, matrix, m, n):
# return 0 means this place ==> 0; 1 ==> don't change
if matrix[m][n] == 0:
return 0
M, N = len(matrix), len(matrix[0])
if any((matrix[m][i] >> 1) == 0 for i in range(N)):
return 0
if any((matrix[i][n] >> 1) == 0 for i in range(M)):
return 0
return 1
``````

``````class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;
const int M = matrix.size(), N = matrix[0].size();
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (matrix[i][j] != 0)
matrix[i][j] = 1 + (matrix[i][j] << 1);
}
}
for (int r = 0; r < M; ++r) {
for (int c = 0; c < N; ++c) {
if (matrix[r][c] == 0) {
for (int j = 0; j < N; ++j) {
matrix[r][j] >>= 1;
matrix[r][j] <<= 1;
}
for (int i = 0; i < M; ++i) {
matrix[i][c] >>= 1;
matrix[i][c] <<= 1;
}
}
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if ((matrix[i][j] & 1) == 1) {
matrix[i][j] >>= 1;
} else {
matrix[i][j] = 0;
}
}
}
}
};
``````

### # 新建数组

``````class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;
vector<vector<int>> newM(matrix);
const int M = matrix.size(), N = matrix[0].size();
for (int r = 0; r < M; ++r) {
for (int c = 0; c < N; ++c) {
if (newM[r][c] == 0) {
for (int j = 0; j < N; ++j) {
matrix[r][j] = 0;
}
for (int i = 0; i < M; ++i) {
matrix[i][c] = 0;
}
}
}
}
}
};
``````

### # 队列

``````class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) return;
const int M = matrix.size(), N = matrix[0].size();
queue<pair<int, int>> q;
for (int r = 0; r < M; ++r) {
for (int c = 0; c < N; ++c) {
if (matrix[r][c] == 0) {
q.push({r, c});
}
}
}
while (!q.empty()) {
auto p = q.front(); q.pop();
for (int j = 0; j < N; ++j) {
matrix[p.first][j] = 0;
}
for (int i = 0; i < M; ++i) {
matrix[i][p.second] = 0;
}
}
}
};
``````

## # 日期

2018 年 9 月 26 日 —— 美好的一周又快要过去了。。 2018 年 12 月 17 日 —— 周一要从早起开始