問題描述

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è)置兩個(gè)長度分別為m和n的標(biāo)記數(shù)組分別記錄行和列是否有0，根據(jù)標(biāo)記數(shù)組將某些矩陣元素置0；
常數(shù)空間方法：只能申請(qǐng)常數(shù)空間，但是可以利用矩陣本身的空間來記錄信息！首先記錄第1行和第1列是否需要置0，這里需要兩個(gè)常數(shù)空間來標(biāo)記，然后用第1行和第1列作為標(biāo)記數(shù)組的空間，來對(duì)除第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