leetcode-73-Set-Matrix-Zeroes

发表于   |  

描述

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:
Did you use extra space?
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?

Subscribe to see which companies asked this question

分析

题意是给定一个二次矩阵，如果某个元素的值是0，设定该行、该列的的值为0。

先考虑最暴力，而且不考虑用额外的存储空间的情况，时间复杂度是$O(n^3)$，而且会有明显的做无用功的情况，比如遍历里某列的时候，整列都置0了，遍历还是要继续，遇到一次0就要重新置0一次。如果是使用额外的存储空间，比如操作一个复制的矩阵，时间复杂度是$O(n^3)$， 空间复杂度是$O(n^2)$。稍稍再细想一下，其实不需要复制整个矩阵，用两个一元的数组就可以存储需要置0的行和列，时间复杂度是$O(n^2)$，空间复杂度是$O(n)。再进一步，其实用矩阵的第一行和第一列进行存储就够了，这里记录的是最佳方案的代码。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int col0 = 1;
        int rows = matrix.size(), cols = matrix[0].size();
        
        for(int i=0; i < rows; i++) {
            if(0 == matrix[i][0]) {
                col0 = 0;
            }
            for(int j=1; j < cols; j++) {
                if(0 == matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        
        for(int i=rows-1; i >= 0; i--) {
            for(int j=cols-1; j >= 1; j--) {
                if(0 == matrix[i][0] || 0 == matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
            if(0 == col0) {
                matrix[i][0] = 0;
            }
        }
    }
};

相关问题

(M) Game of Life

题目来源