网站导航栏设计步骤2020年十大关键词

39 矩阵置零

39.1 矩阵置零解决方案

解题思路：

• 利用第一行和第一列标记：
  • 使用两个标记变量，rowZero和colZero，来判断第一行和第一列是否需要置零。
  • 遍历矩阵从(1,1)开始，如果某个元素是0，则标记该行和该列的第一个元素为0.
  • 最后根据标记来处理第一行和第一列。
• 步骤
  • 遍历矩阵，将遇到0的行和列的第一个元素设置为0.
  • 遍历结束后，根据第一行和第一列的标记，置零相应的位置。
  • 最后特别处理第一行和第一列，依据rowZero和colZero来决定是否置零。

class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();// 标记第一行和第一列是否需要置零bool rowZero = false;bool colZero = false;// 检查第一行是否包含0for(int i = 0 ; i < n ;i++){if(matrix[0][i] == 0){rowZero = true;break;}}// 检查第一行是否包含0for(int i = 0 ; i < m ;i++){if(matrix[i][0] == 0){colZero = true;break;}}// 用第一行和第一列来标记需要置零的行和列for(int i = 1; i < m ; i++ ){for(int j = 1; j < n ; j++){if(matrix[i][j] == 0){matrix[i][0] = 0; // 标记所在行的第一列matrix[0][j] = 0; // 标记所在列的第一行}}}for(int i = 1; i < m ; i++ ){for(int j = 1; j < n ; j++){if(matrix[i][0] == 0 || matrix[0][j] == 0){matrix[i][j] = 0;}}}// 处理第一行是否需要置零if(rowZero){for(int i = 0; i < n; i++){matrix[0][i] = 0;}}// 处理第一列是否需要置零if(colZero){for(int i = 0; i < m ; i++){matrix[i][0] = 0;}}}
};

代码解释：

• 标记第一行和第一列：
  • 先通过两个标记变量rowZero和colZero来记录第一行和第一列是否需要置零。
  • 遍历整个矩阵，如果某个元素是0 ，则将其对应的第一行和第一列元素置为0，表示这一行和这一列都需要被置零。
• 根据标记置零：
  • 第二次遍历矩阵(从(1，1)开始)，根据第一行和第一列的标记，把相应的元素置为0.
• 处理第一列和第一行：
  • 最后，检查rowZero和colZero，如果需要，就把第一行和第一列的所有元素置为0.

时间复杂度和空间复杂度：

• 时间复杂度：$O(m\ast n)$，其中m 和 n 是矩阵的行数和列数。我们遍历了矩阵几次，每次遍历都是$O(m\ast n)$的时间复杂度。
• 空间复杂度：$O(1$,因为我们只用了常数空间(除了原矩阵)。

39.2 举例说明

假设有以下矩阵：

1  2  3
4  0  6
7  8  9

• 初始化标记：

  • rowZero：用来判断第一行是否需要置零。
  • colZero：用来判断第一列是否需要置零。
    初始状态：

• rowZero = false (假设第一行不需要置零)

• colZero = false (假设第一行不需要置零)

• 检查第一行和第一列是否包含零

  • 检查第一行：
    • 第一行是1 2 3 ，没有0，因此rowZero不变，仍然为false。
  • 检查第一列：
    • 第一列是1 4 7，没有 0，因此colZero不变，仍然为false。

• 使用第一行和第一列标记需要置零的行和列
  矩阵如下：

1  2  3
4  0  6
7  8  9

• 遍历(1,1):值是0，因此我们将martix[1][0]和martix[0][1]都置为0，表示第二行和第二列需要置零。此时矩阵变为：

1  2  3
0  0  6
7  8  9

• 遍历 (1,2)：值是 6，不需要做任何操作。
• 遍历 (2,1)：值是 7，不需要做任何操作。
• 遍历 (2,2)：值是 8，不需要做任何操作。

矩阵变为：

1  2  3
0  0  6
7  8  9

• 根据标记置零
  • 处理第二行
    • 因为martix[1][0]是0,所以整个第二行需要置零。矩阵变为：

    1  2  3
    0  0  0
    7  8  9
    

  • 处理第三例：
    • 因为 matrix[0][2] 是 0，所以整个第三列需要置零。矩阵变为：

    1  2  0
    0  0  0
    7  8  0
    

• 处理第一行和第一列
  • 处理第一行：
    • 由于rowZero = false,第一行不需要置零，因此保持不变。
  • 处理第一列：
    • 由于colZero = false,第一列不需要置零，因此也保持不变。
      最终矩阵：

1  2  0
0  0  0
7  8  0