Keshawn_lu's Blog

Leetcode 面试题 01.08. 零矩阵

字数统计: 261阅读时长: 1 min
2022/09/30 Share

题目简介：

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

思路：

设置一个标记数组，若本身元素不为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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {

        vector<vector<int>> flag(matrix.size(), vector<int>(matrix[0].size()));

        for(int i = 0; i < matrix.size(); i++){

            for(int j = 0; j < matrix[i].size(); j++){

                if(flag[i][j] == 1)
                    continue;

                if(matrix[i][j] == 0){

                    for(int k = 0; k < matrix.size(); k++){

                        if(matrix[k][j] != 0){

                            matrix[k][j] = 0;
                            flag[k][j] = 1;
                        }
                        
                    }
                        
                    for(int k = 0; k < matrix[i].size(); k++){

                        if(matrix[i][k] != 0){

                            matrix[i][k] = 0;
                            flag[i][k] = 1;
                        }
                    }
                }
            }
        }
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网