成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Set Matrix Zeroes 矩陣置零

waltr / 3358人閱讀

摘要：這個方法的缺點在于，如果我們直接將存入首行或首列來表示相應(yīng)行和列要置的話，我們很難判斷首行或者首列自己是不是該置。

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.


click to show follow up.


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?
新建矩陣法 復(fù)雜度

時間 O(NM) 空間 O(NM)

思路

最簡單的方法就是建一個同樣大小的矩陣，在原矩陣中遇到一個0，就將新矩陣的行和列設(shè)為0

首行首列暫存法 復(fù)雜度

時間 O(NM) 空間 O(1)

思路

實際上，我們只需要直到哪些行，哪些列需要被置0就行了，最簡單的方法就是建兩個大小分別為M和N的數(shù)組，來記錄哪些行哪些列應(yīng)該被置0。那有沒有可能不用額外空間呢？我們其實可以借用原矩陣的首行和首列來存儲這個信息。這個方法的缺點在于，如果我們直接將0存入首行或首列來表示相應(yīng)行和列要置0的話，我們很難判斷首行或者首列自己是不是該置0。這里我們用兩個boolean變量記錄下首行和首列原本有沒有0，然后在其他位置置完0后，再多帶帶根據(jù)boolean變量來處理首行和首列，就避免了干擾的問題。

代碼 
public class Solution {
    public void setZeroes(int[][] matrix) {
        if(matrix.length == 0) return;
        boolean firstRowZero = false, firstColZero = false;
        // 記錄哪些行哪些列需要置0，并判斷首行首列是否需要置0
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                if(i != 0 && j != 0 && matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                } else if (matrix[i][j] == 0){
                    // 如果首行或首列出現(xiàn)0，則標(biāo)記其需要置0，否則沿用上次值
                    firstRowZero = i == 0 ? true : firstRowZero;
                    firstColZero = j == 0 ? true : firstColZero;
                }
            }
        }
        // 將除首行首列的位置置0
        for(int i = 1; i < matrix.length; i++){
            for(int j = 1; j < matrix[0].length; j++){
                if(matrix[0][j] == 0 || matrix[i][0] == 0){
                    matrix[i][j] = 0;
                }
            }
        }
        // 如果必要，將首列置0
        for(int i = 0; firstColZero && i < matrix.length; i++){
            matrix[i][0] = 0;
        }
        // 如果必要，將首行置0
        for(int j = 0; firstRowZero && j < matrix[0].length; j++){
            matrix[0][j] = 0;
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64526.html

相關(guān)文章

  • [LintCode/LeetCode/CC] Set Matrix Zeroes

    摘要：把矩陣所有零點的行和列都置零，要求不要額外的空間。對于首行和首列的零點，進行額外的標(biāo)記即可。這道題我自己做了四遍，下面幾個問題需要格外注意標(biāo)記首行和首列時，從到遍歷時，若有零點，則首列標(biāo)記為從到遍歷，若有零點，則首行標(biāo)記為。 Problem Given a m x n matrix, if an element is 0, set its entire row and column t...

    zhangwang 評論0 收藏0

  • LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

    摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數(shù)組知識點?；蛘呃奖疚淖钕旅?，添加的微信等會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

    tracy 評論0 收藏0

  • leetcode73. Set Matrix Zeroes

    摘要：題目要求當(dāng)遇到數(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....

    lookSomeone 評論0 收藏0

  • LeetCode 精選TOP面試題【51 ~ 100】

    摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復(fù)雜度為 ...

    Clect 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<