leetcode73. Set Matrix Zeroes

lookSomeone 發(fā)布于2019-08-15 10:48 / 2307人閱讀

摘要：題目要求當遇到數(shù)組中的值時，即將該值所在的行和列全部改為。新建兩個數(shù)組分別代表該行和該列是否需要清零。然后根據(jù)這兩個數(shù)組的情況對原數(shù)組進行賦值。雖然這意味著犧牲了一點時間性能，但是如果數(shù)據(jù)量非常龐大的話是非常好的一種實現(xiàn)。

題目要求

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?

當遇到數(shù)組中的值時，即將該值所在的行和列全部改為0。

思路一：O(m+n）

這里題目中給出了三種空間復雜度。
第一種是O(mn），也就是新建一個boolean[m][n]的二維數(shù)組，如果該行列上值為0，則將其對應位置上的值也設置為0.最后再遍歷boolean[][]，將true所在的行列設置為0。但是這種方法不僅boolean[][]中很多值用不到，還會導致重復的0賦值行為，效率很低。
這里給出O(m+n)空間復雜度的方法。新建兩個boolean[]數(shù)組分別代表該行和該列是否需要清零。然后根據(jù)這兩個數(shù)組的情況對原數(shù)組進行賦值。代碼如下：

    public void setZeroes(int[][] matrix) {
        int rowCount = matrix.length;
        if(matrix.length==0){
            return;
        }
        int columnCount = matrix[0].length;
        boolean[] rowIsZero = new boolean[rowCount];
        boolean[] columnIsZero = new boolean[columnCount];
        for(int i = 0 ; i
思路二：O(1)空間復雜度
其實我們可以發(fā)現(xiàn)，如果我們將原數(shù)組中其中的一行和一列利用了來存儲當前行和列的清零情況，還可以節(jié)約更多的時間和空間。雖然這意味著犧牲了一點時間性能，但是如果數(shù)據(jù)量非常龐大的話是非常好的一種實現(xiàn)。代碼如下：
    public void setZeroes2(int[][] matrix) {
        if(matrix==null){
            return;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        boolean rowHasZero = false;
        boolean colHasZero = false;
        
        for(int i=0; i

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~