LeetCode 73 - Set Matrix Zero

作者 QIFAN 日期 2017-01-19
LeetCode 73 - Set Matrix Zero

原题链接: 73. Set Matrix Zero


题干

给定一个 m * n 的矩阵,如果其中某一个元素为 0 ,那将该元素所在行与列的元素的值都设为 0 。 in-place 操作。

思路

之所以会用到额外空间是因为要记录当前每行每列的状态,若状态可以用一个常数空间的数据结构来表示。对于某行或某列,决定它是不是会清零的条件就是这一行/列有没有 0 。“有”或“没有”,这让我想到了二进制。能不能用一串二进制数字来表示状态。这样需要知道 m 和 n 的范围。假设可以放下。

解法如下:

  • 新建两个 int 变量 rowState 与 colState 分别表示行与列的状态。
  • 遍历矩阵,如果 matrix[row][col] == 0 ,记录状态:
    • rowState |= 1 << row;
    • colState |= 1 << col;
  • 状态记录完毕,进行清零:
    for row in 1..m:
    if rowState & (1 << row) == 1):
    paint all row to 0
    col 同理

代码:

public void setZeroes(int[][] matrix) {
int M = matrix.length;
int N = matrix[0].length;
int rowState = 0;
int colState = 0;
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
// 标记这一行这一列有 0
if (matrix[row][col] == 0) {
rowState |= 1 << row;
colState |= 1 << col;
}
}
}
for (int row = 0; row < M; row++) {
if (rowState & (1 << row) > 1) {
int col = 0;
while(col < N) {
matrix[row][col++] = 0;
}
}
}
for (int col = 0; col < N; col++) {
if (colState & (1 << col) > 1) {
int row = 0;
while(row < M) {
matrix[row++][col] = 0;
}
}
}
}

对于小矩阵是可行的,但是后面矩阵宽度 > 20 时就因为整形溢出而出错了。然后就考虑用 string 吧。

public void setZeroes(int[][] matrix) {
int M = matrix.length;
int N = matrix[0].length;
StringBuilder rowState = new StringBuilder();
StringBuilder colState = new StringBuilder();
for (int row = 0; row < M; row++) {
rowState.append(0);
}
for (int col = 0; col < N; col++) {
colState.append(0);
}
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
// 标记这一行这一列有 0
if (matrix[row][col] == 0) {
rowState.setCharAt(row, 1);
colState.setCharAt(col, 1);
}
}
}
System.out.println("rowState=" + rowState + ", colState=" + colState);
for (int row = 0; row < M; row++) {
if (rowState.charAt(row) == '1') {
int col = 0;
while(col < N) {
matrix[row][col++] = 0;
}
}
}
for (int col = 0; col < N; col++) {
if (colState.charAt(col) == '1') {
int row = 0;
while(row < M) {
matrix[row++][col] = 0;
}
}
}
}

当然更实在的方法应该是把状态存到第一行与第一列。。代码就不写了。