Leetcode 73 Set Matrix Zeroes

在这里插入图片描述
思路一: space complexity为O(m+n),虽然题目要求O(1),但是我一开始只能想到这个方法,所以还是实现了一下。Anyway, it’s not too bad。将复杂度控制在m+n是因为用了set。set里存放需要置0的行和列。思路很简单,直接展示代码:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        Set<Integer> row = new HashSet<>();
        Set<Integer> col = new HashSet<>();
        for(int i = 0; i < m ; i++){
            for(int j = 0; j < n; j++){
               if(matrix[i][j] == 0){
                   row.add(i);   
               } 
            }
        }
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
               if(matrix[j][i] == 0){
                   col.add(i);   
               } 
            }
        }
        
        for(Integer i : row){
            for(int k = 0; k < n; k++){matrix[i][k] = 0;}
        }
        
        for(Integer i : col){
            for(int k = 0; k < m; k++){matrix[k][i] = 0;}
        }
        
    }
}

思路二: time complexity O(1)。其实这个方法在我思考的时候曾经从脑子里闪过,但是很可惜我没有深究。基本想法是先遍历整个matrix,碰到0,就把该元素所在的行与列的第一个元素置0(每一行和每一列的第一个元素相当于一个flag,标记着这一行(列)是否需要置0)。但是这边有两个special cases,第一行和第一列需要单独考虑。因为matrix[0][0]不仅仅代表第一行,还代表第一列。如果matrix[0][0]为0,我们无法确定到底是要将第一行置0还是将第一列置0还是将第一行和第一列都置0。下面展示代码:

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int judgeRow = 0;
        int judgeCol = 0;
        
        // 判断第一行和第一列有没有0
        for(int i = 0; i < n; i++){
            if(matrix[0][i] == 0) judgeRow = 1;
        }
        for(int i = 0; i < m; i++){
            if(matrix[i][0] == 0) judgeCol = 1;
        }
        
        // 标记哪些行和哪些列需要置0
        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;
                }
            }
        }
        
        // 从第二行开始,置0操作,留下第一行待会单独考虑
        for(int i = 1; i < m; i++){
            if(matrix[i][0] == 0){
                for(int j = 0; j < n; j++){
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 从第二列开始,置0操作,留下第一列待会单独考虑
        for(int i = 1; i < n; i++){
            if(matrix[0][i] == 0){
                for(int j = 0; j < m; j++){
                    matrix[j][i] = 0;
                }
            }
        }
        
        // 第一行与第一列单独考虑
        if(judgeCol == 1){
            for(int i = 0; i < m; i++){
                matrix[i][0] = 0;
            }
        }
        if(judgeRow == 1){
            for(int i = 0; i < n; i++){
                matrix[0][i] = 0;
            }
        } 
    }
}

总结: 无

热门文章

暂无图片
编程学习 ·

SpringBoot解决跨域

第一种:书写解决跨域的类public class AccessControlAllowOriginFilter implements Filter {@Overridepublic void init(FilterConfig filterConfig) throws ServletException {}@Overridepublic void doFilter(ServletRequest req, ServletResponse res, FilterChain chain) …
暂无图片
编程学习 ·

离线安装pyinstaller时,报错的解决过程

报错内容: Command ““c:\program files\python37\python.exe” “c:\program files\python37\lib\site-packages\pip” install --ignore-installed --no-user --prefix C:\Users\yf\AppData\Local\Temp\pip-build-env-l034cdvw\overlay --no-warn-script-location --no-bina…
暂无图片
编程学习 ·

[云盘](二)我的文件和共享列表后台实现

后台代码实现我的文件列表Mian读取配置信息解析json登录token(cmd为count)解析jason(cmd不为count)获取用户文件个数获取用户文件列表源码共享文件列表main获取共享文件个数前端分页请求包获得普通共享文件列表共享文件排行榜源码 我的文件列表业务逻辑是,点击我的文件,会…
暂无图片
中恒嘉业 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
cgfy ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…
暂无图片
coreui ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
coreui ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
未来博客 ·

Heap Sort 讲解

Heap Sort sorts a group of unordered elements using the Heap data structure. The sorting algorithm using a Min Heap is as follows: Heapify all elements into a Min HeapRecord and delete the top elementPut to top element into an array T that stores all so
暂无图片
未来博客 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
建站日记 ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
建站日记 ·

STL Practice —— 【map (1)】

Description 给出学生姓名和分数&#xff0c;要求你输入姓名查询分数。 Input 输入包含T组测试数据。 开头是一个正整数T (0<T<10)&#xff0c;为测试数据数量。 对于每组测试数据&#xff0c;第一行是一个正整数N (0<N<100000)。 接下来有N行&#xff0c;每行包…
暂无图片
mfbz ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
mfbz ·

[react] 你觉得react上手快不快?它有哪些限制?

[react] 你觉得react上手快不快&#xff1f;它有哪些限制&#xff1f; 相对vue来说不快。 限制 需要学习JSX需要工程化的配置需要对原生JavaScript有相当的掌握react只是一个UI层面的库&#xff0c;像vue内置了动画处理、keep-alive等功能&#xff0c;react则需要去找第三方库…
暂无图片
珊珊日记 ·

AOV网是否存在回路-拓扑排序-C++

拓扑排序是对测试AOV网是否存在回路的方法&#xff01; 拓扑排序的过程中&#xff0c;由于需要查找所有以某顶点为尾的弧&#xff0c;即找到该顶点的所有出边&#xff0c;故图要采用邻接表的存储方式。但拓扑排序较邻接表的存储方式有一点不同&#xff0c;由于要查找入度为0的点…
暂无图片
珊珊日记 ·

8. 源码分析之ConsumeQueue

源码分析之ConsumeQueue 消息发送时数据在ConsumeQueue的落地 ​ 连续发送5条消息&#xff0c;消息是不定长&#xff0c;首先所有信息先放入 Commitlog中&#xff0c;每一条消息放入Commitlog的时候都需要上锁&#xff0c;确保顺序的写入。 ​ 当Commitlog写成功了之后。数据…