LeetCode_Array_73. Set Matrix Zeroes (C++)

目录

​​1，题目描述​​

​​2，思路​​

​​3，代码【C++】​​

​​4，测试效果​​

1，题目描述

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
Output: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

Input: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
Output: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

    A straight forward solution using O(mn) space is probably a bad idea.
    A simple improvement uses O(m + n) space, but still not the best solution.
    Could you devise a constant space solution?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2，思路

参考了LeetCode的官方题解，核心思想是：将第一行/列作为标记，遍历矩阵内元素（除了第一行/列），若某一元素值为0，则修改其在第一行/列对应位置的值为0，根据此标记对矩阵元素进行赋值；

具体算法：

1. 设rowTag和colTag来标记原始矩阵中的第一行/列是否含0（因为后面做标记时，可能会弄混第一行/列原来是否含0），并根据矩阵元素赋予相应的值；
2. 第一次遍历，对矩阵元素进行遍历（从左向右，从上到下），若matrix[i][j] == 0，则matrix[i][0] = 0，matrix[0][j] = 0；
3. 第二次遍历，从matrix[1][1]开始，根据标记重置元素（除第一行/列）；
4. 根据rewTag和colTag，处理第一行/列；

3，代码【C++】

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        bool rowTag = false;    //在第一行原始数据中是否含0
        bool colTag = false;    //在第一列原始数据中是否含0

        for(int i = 0 ; i < n ; i++){
            if(matrix[0][i] == 0) rowTag = true;
        }
        for(int i = 0 ; i < m ; i++){
            if(matrix[i][0] == 0) colTag = true;
        }
        
        //第一次遍历 在第一行/列做标记
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; 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(rowTag) {
            for(int i = 0 ; i < n ; i++) matrix[0][i] = 0;
        }
        if(colTag) {
            for(int i = 0 ; i < m ; i++) matrix[i][0] = 0;
        }
    }
};

4，测试效果

经历过上次的测试后，emmm，仅供参考吧，hhh