摘要:題目要求當遇到數組中的值時,即將該值所在的行和列全部改為。新建兩個數組分別代表該行和該列是否需要清零。然后根據這兩個數組的情況對原數組進行賦值。雖然這意味著犧牲了一點時間性能,但是如果數據量非常龐大的話是非常好的一種實現。
題目要求
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?
當遇到數組中的值時,即將該值所在的行和列全部改為0。
思路一:O(m+n)這里題目中給出了三種空間復雜度。
第一種是O(mn),也就是新建一個boolean[m][n]的二維數組,如果該行列上值為0,則將其對應位置上的值也設置為0.最后再遍歷boolean[][],將true所在的行列設置為0。但是這種方法不僅boolean[][]中很多值用不到,還會導致重復的0賦值行為,效率很低。
這里給出O(m+n)空間復雜度的方法。新建兩個boolean[]數組分別代表該行和該列是否需要清零。然后根據這兩個數組的情況對原數組進行賦值。代碼如下:
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)空間復雜度 其實我們可以發現,如果我們將原數組中其中的一行和一列利用了來存儲當前行和列的清零情況,還可以節約更多的時間和空間。雖然這意味著犧牲了一點時間性能,但是如果數據量非常龐大的話是非常好的一種實現。代碼如下:
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
想要了解更多開發技術,面試教程以及互聯網公司內推,歡迎關注我的微信公眾號!將會不定期的發放福利哦~
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/67358.html
摘要:這個方法的缺點在于,如果我們直接將存入首行或首列來表示相應行和列要置的話,我們很難判斷首行或者首列自己是不是該置。 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...
摘要:把矩陣所有零點的行和列都置零,要求不要額外的空間。對于首行和首列的零點,進行額外的標記即可。這道題我自己做了四遍,下面幾個問題需要格外注意標記首行和首列時,從到遍歷時,若有零點,則首列標記為從到遍歷,若有零點,則首行標記為。 Problem Given a m x n matrix, if an element is 0, set its entire row and column t...
摘要:每天會折騰一道及以上題目,并將其解題思路記錄成文章,發布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中,做了匯總了數組知識點。或者拉到本文最下面,添加的微信等會根據題解以及留言內容,進行補充,并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
摘要:前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫~現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。 順序整理 1~50 1...
摘要:題目鏈接題目分析給定一個整數數組,將值為的元素移動到數組末尾,而不改動其他元素出現的順序。再在去后的元素末尾填充到計算出的數組長度。最終代碼若覺得本文章對你有用,歡迎用愛發電資助。 D68 283. Move Zeroes 題目鏈接 283. Move Zeroes 題目分析 給定一個整數數組,將值為0的元素移動到數組末尾,而不改動其他元素出現的順序。 思路 計算總共有多少個元素。 再...
閱讀 2665·2021-11-24 10:44
閱讀 1920·2021-11-22 13:53
閱讀 1948·2021-09-30 09:47
閱讀 3712·2021-09-22 16:00
閱讀 2443·2021-09-08 09:36
閱讀 2321·2019-08-30 15:53
閱讀 2795·2019-08-30 15:48
閱讀 990·2019-08-30 15:44