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: Could you devise a constant space solution?

問題分析

簡單方法:設(shè)置兩個長度分別為m和n的標(biāo)記數(shù)組分別記錄行和列是否有0,根據(jù)標(biāo)記數(shù)組將某些矩陣元素置0即供;
常數(shù)空間方法:只能申請常數(shù)空間某残,但是可以利用矩陣本身的空間來記錄信息此熬!首先記錄第1行和第1列是否需要置0龄坪,這里需要兩個常數(shù)空間來標(biāo)記腾窝,然后用第1行和第1列作為標(biāo)記數(shù)組的空間堆生,來對除第1行和第1列之外的行和列進(jìn)行記錄虐译。最后根據(jù)記錄將某些矩陣元素置0。

AC代碼

#encoding=utf-8
class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        # 注釋掉的是O(mn)空間的方法
        # m = len(matrix)
        # if m == 0:
        #     return matrix
        # n = len(matrix[0])
        # if n == 0:
        #     return matrix
        # flag_row = [False for i in range(m)]
        # flag_column = [False for i in range(n)]

        # for i in range(m):
        #     for j in range(n):
        #         if matrix[i][j] == 0:
        #             flag_row[i] = True
        #             flag_column[j] = True

        # for i in range(m):
        #     for j in range(n):
        #         if flag_row[i] or flag_column[j]:
        #             matrix[i][j] = 0

        #下面是常數(shù)空間的算法
        m = len(matrix)
        if m == 0:
            return matrix
        n = len(matrix[0])
        if n == 0:
            return matrix
        flag_row = False
        flag_column = False

        #記錄第1行和第1列是否置0
        for i in range(n):
            if matrix[0][i] == 0:
                flag_row = True
                break
        for j in range(m):
            if matrix[j][0] == 0:
                flag_column = True
                break

        #用第1行和第1列記錄其他行和列是否置0
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[0][j] = 0
                    matrix[i][0] = 0

        #改變其他行和列的值
        for i in range(1, m):
            for j in range(1, n):
                if matrix[0][j] == 0 or matrix[i][0] == 0:
                    matrix[i][j] = 0

        #改變第一行和第一列的值
        if flag_row:
            for j in range(n):
                matrix[0][j] = 0
        if flag_column:
            for i in range(m):
                matrix[i][0] = 0
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末鹅龄,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子亭畜,更是在濱河造成了極大的恐慌扮休,老刑警劉巖,帶你破解...
    沈念sama閱讀 211,123評論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拴鸵,死亡現(xiàn)場離奇詭異玷坠,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)劲藐,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,031評論 2 384
  • 文/潘曉璐 我一進(jìn)店門八堡,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人聘芜,你說我怎么就攤上這事兄渺。” “怎么了汰现?”我有些...
    開封第一講書人閱讀 156,723評論 0 345
  • 文/不壞的土叔 我叫張陵挂谍,是天一觀的道長。 經(jīng)常有香客問我瞎饲,道長口叙,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 56,357評論 1 283
  • 正文 為了忘掉前任嗅战,我火速辦了婚禮妄田,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘驮捍。我一直安慰自己疟呐,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,412評論 5 384
  • 文/花漫 我一把揭開白布厌漂。 她就那樣靜靜地躺著萨醒,像睡著了一般。 火紅的嫁衣襯著肌膚如雪苇倡。 梳的紋絲不亂的頭發(fā)上富纸,一...
    開封第一講書人閱讀 49,760評論 1 289
  • 那天囤踩,我揣著相機(jī)與錄音,去河邊找鬼晓褪。 笑死堵漱,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的涣仿。 我是一名探鬼主播勤庐,決...
    沈念sama閱讀 38,904評論 3 405
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼好港!你這毒婦竟也來了愉镰?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 37,672評論 0 266
  • 序言:老撾萬榮一對情侶失蹤钧汹,失蹤者是張志新(化名)和其女友劉穎丈探,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體拔莱,經(jīng)...
    沈念sama閱讀 44,118評論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡碗降,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,456評論 2 325
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了塘秦。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片讼渊。...
    茶點(diǎn)故事閱讀 38,599評論 1 340
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖尊剔,靈堂內(nèi)的尸體忽然破棺而出爪幻,到底是詐尸還是另有隱情,我是刑警寧澤赋兵,帶...
    沈念sama閱讀 34,264評論 4 328
  • 正文 年R本政府宣布笔咽,位于F島的核電站,受9級特大地震影響霹期,放射性物質(zhì)發(fā)生泄漏叶组。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,857評論 3 312
  • 文/蒙蒙 一历造、第九天 我趴在偏房一處隱蔽的房頂上張望甩十。 院中可真熱鬧,春花似錦吭产、人聲如沸侣监。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,731評論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽橄霉。三九已至,卻和暖如春邑蒋,著一層夾襖步出監(jiān)牢的瞬間姓蜂,已是汗流浹背按厘。 一陣腳步聲響...
    開封第一講書人閱讀 31,956評論 1 264
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留钱慢,地道東北人逮京。 一個月前我還...
    沈念sama閱讀 46,286評論 2 360
  • 正文 我出身青樓,卻偏偏與公主長得像束莫,于是被迫代替她去往敵國和親懒棉。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,465評論 2 348

推薦閱讀更多精彩內(nèi)容