39 矩阵置零

39 矩阵置零

39.1 矩阵置零办理方案

解题思路：

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

1. class Solution {
2. public:
3.     void setZeroes(vector<vector<int>>& matrix) {
4.         int m = matrix.size();
5.         int n = matrix[0].size();
7.         // 标记第一行和第一列是否需要置零
8.         bool rowZero = false;
9.         bool colZero = false;
11.         // 检查第一行是否包含0
12.         for(int i = 0 ; i < n ;i++){
13.             if(matrix[0][i] == 0){
14.                 rowZero = true;
15.                 break;
16.             }
17.         }
19.         // 检查第一行是否包含0
20.         for(int i = 0 ; i < m ;i++){
21.             if(matrix[i][0] == 0){
22.                 colZero = true;
23.                 break;
24.             }
25.         }
27.         // 用第一行和第一列来标记需要置零的行和列
28.         for(int i = 1; i < m ; i++ ){
29.             for(int j = 1; j < n ; j++){
30.                 if(matrix[i][j] == 0){
31.                     matrix[i][0] = 0; // 标记所在行的第一列
32.                     matrix[0][j] = 0; // 标记所在列的第一行
33.                     
34.                 }
35.             }
36.         }
38.         for(int i = 1; i < m ; i++ ){
39.             for(int j = 1; j < n ; j++){
40.                 if(matrix[i][0] == 0 || matrix[0][j] == 0){
41.                     matrix[i][j] = 0;
42.                 }
43.             }
44.         }
46.         // 处理第一行是否需要置零
47.         if(rowZero){
48.             for(int i = 0; i < n; i++){
49.                 matrix[0][i] = 0;
50.             }
51.         }
53.         // 处理第一列是否需要置零
54.         if(colZero){
55.             for(int i = 0; i < m ; i++){
56.                 matrix[i][0] = 0;
57.             }
58.         }
59.     }
60. };

复制代码

代码解释：

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

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

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

39.2 举例阐明

假设有以下矩阵：

1. 1  2  3
2. 4  0  6
3. 7  8  9

复制代码

• 初始化标志：
  
  
  
  • rowZero：用来判定第一行是否必要置零。
    
  • colZero：用来判定第一列是否必要置零。
    初始状态：
    
  
  
• rowZero = false (假设第一行不必要置零)
  
• colZero = false (假设第一行不必要置零)
  
• 检查第一行和第一列是否包罗零
  
  
  
  • 检查第一行：
    
    
    
    • 第一行是1 2 3 ，没有0，因此rowZero稳定，仍旧为false。
      
    
    
  • 检查第一列：
    
    
    
    • 第一列是1 4 7，没有 0，因此colZero稳定，仍旧为false。
      
    
    
  
  
• 使用第一行和第一列标志必要置零的行和列
  矩阵如下：
  

1. 1  2  3
2. 4  0  6
3. 7  8  9

复制代码

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

1. 1  2  3
2. 0  0  6
3. 7  8  9

复制代码

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

矩阵变为：

1. 1  2  3
2. 0  0  6
3. 7  8  9

复制代码

• 根据标志置零
  
  
  
  • 处理第二行
    
    
    
    • 因为martix[1][0]是0,所以整个第二行必要置零。矩阵变为：
      
    1. 1  2  3
    2. 0  0  0
    3. 7  8  9

    复制代码
    
    
  • 处理第三例：
    
    
    
    • 因为 matrix[0][2] 是 0，所以整个第三列必要置零。矩阵变为：
      
    1. 1  2  0
    2. 0  0  0
    3. 7  8  0

    复制代码
    
    
  
  
• 处理第一行和第一列
  
  
  
  • 处理第一行：
    
    
    
    • 由于rowZero = false,第一行不必要置零，因此保持稳定。
      
    
    
  • 处理第一列：
    
    
    
    • 由于colZero = false,第一列不必要置零，因此也保持稳定。
      终极矩阵：
      
    
    
  
  

1. 1  2  0
2. 0  0  0
3. 7  8  0

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。