73. Set Matrix Zeroes 矩阵置零

作者：负雪明烛 id： fuxuemingzhu 个人博客： https://fuxuemingzhu.cn/

题目地址：https://leetcode.com/problems/set-matrix-zeroes/description/

题目描述

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]
]

Follow up:

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

题目大意

有一个二维矩阵，如果某一个位置出现了0，那么这个0所在的行和列全部转化成0. 原地操作。

解题方法

原地操作

最简单的方法就是用一个新的二维矩阵保存每个位置的结果，最后再放回原地了，题目说了这样不好。

一个简单的优化是，只需要保存每行和每列是否应该置为0，这样用了O(m+n)的空间，但是还有更好的解法。

我想了一个不用额外空间的，暴力的解法。时间上也勉强通过了。。

这个题和289. Game of Life比较像，289题只用判断8-连通，而这个题需要判断一整行。

我使用的方法是将每个位置的元素的二进制再增加一位，也就是说在末尾补上一个0或者1代表这个是否应该变成0或者不变。如果经过遍历之后，发现最后一位是0，那么把这个位置的数字变成0，如果最后一位是1，那么把这个位置的数字还原成原来的数字（右移一位）。

由于每个数字记录它的状态是在原地进行的，所以我说没有用到额外的空间。但这个题不好的地方在于，第一，没有说出MN的范围，让我很难判断这个解法能否通过；第二，没有说出matrix[m][n]的范围，不能判断左移一位之后，整数是否溢出（Python不存在这个问题）。

时间复杂度是O((M*N) * (M + N))，空间复杂度是O(1).

时间复杂度有(M + N)是因为，对于每个位置都去把这个行、列的所有数值进行了遍历来判断是否存在0，其实可以通过把结果保存到这个行列的第一个位置即可，降低了判断的时间复杂度。

代码如下：

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

这个解法本身是有问题的，如果左移超出INT最大值的时候。比如C++这个方法就过不了。测试用例果然有个INT最大值，这样左移就超出范围了，下面解法是错的。

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;
                }
            }
        }
    }
};

新建数组

如果使用新的数组，把老数组拷贝一份，那么就可以在原数组上进行判断，在新数组上进行修改，也就是题目说的O(MN)的空间复杂度。

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;
                    }
                }
            }
        }
    }
};

队列

使用一个队列保存出现过0的位置，然后就可以再次遍历把所有的位置设置为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 日 —— 周一要从早起开始