【leetcode】73. 矩阵置零（python）_矩阵置零 python

思维误区：原地算法允许使用少量额外的辅助变量，不是完全不能用额外空间的

原地算法 定义：在计算机科学中，一个原地算法（in-place algorithm）基本上不需要额外辅助的数据结构，然而，允许少量额外的辅助变量来转换数据的算法。当算法运行时，输入的数据通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。–摘自维基百科。

方法一：使用标记数组，标记该行该列是否有0元素

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        row, col = [False] * m, [False] * n         
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True
        for i in range(m):
            for j in range(n):
                if row[i] or col[j]:
                    matrix[i][j] = 0
        return matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方法二：使用一个标记变量

        # 优化版本，方法二：
        # 1.遍历查看首行是否有0，并用flag_col0标记；
        # 2.遍历每一个元素，并将0元素所在的行和列，标记到首行和首列位置
        # 3.倒序遍历查看首行首列是否有0元素，若有0，则将该行该列置为0
        # 4.根据flag_col0, 处理首行元素
class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        flag_col0 = False
        
        for i in range(m):
            if matrix[i][0] == 0:
                flag_col0 = True
            for j in range(1, n): # (1,n)
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0   # 标记到首行首列
        for i in range(m-1, -1, -1):  # 倒序遍历
            for j in range(1, n):    
                if matrix[i][0] ==0 or matrix[0][j] == 0: # 查看首行首列是否有0元素
                    matrix[i][j] = 0  # 若有0，则将该行该列置为0
            if flag_col0:  # 若首行有0，则将首行的所有元素置为0
                matrix[i][0] = 0    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

详细介绍请看官方题解：官方题解 ，本文仅作为个人 take notes.