今天小编给大家分享一下C++如何实现矩阵赋零的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。
创新互联是一家专业提供正阳企业网站建设,专注与成都网站设计、成都网站制作、H5技术、小程序制作等业务。10年已为正阳众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
click to show follow up.
Follow up:
Did you use extra space?
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?
据说这题是CareerCup上的原题,我还没有刷CareerCup,所以不知道啦,不过这题也不算难,虽然我也是看了网上的解法照着写的,但是下次遇到绝对想的起来。这道题中说的空间复杂度为O(mn)的解法自不用多说,直接新建一个和matrix等大小的矩阵,然后一行一行的扫,只要有0,就将新建的矩阵的对应行全赋0,行扫完再扫列,然后把更新完的矩阵赋给matrix即可,这个算法的空间复杂度太高。将其优化到O(m+n)的方法是,用一个长度为m的一维数组记录各行中是否有0,用一个长度为n的一维数组记录各列中是否有0,最后直接更新matrix数组即可。这道题的要求是用O(1)的空间,那么我们就不能新建数组,我们考虑就用原数组的第一行第一列来记录各行各列是否有0.
- 先扫描第一行第一列,如果有0,则将各自的flag设置为true
- 然后扫描除去第一行第一列的整个数组,如果有0,则将对应的第一行和第一列的数字赋0
- 再次遍历除去第一行第一列的整个数组,如果对应的第一行和第一列的数字有一个为0,则将当前值赋0
- 最后根据第一行第一列的flag来更新第一行第一列
代码如下:
class Solution { public: void setZeroes(vector<vector<int> > &matrix) { if (matrix.empty() || matrix[0].empty()) return; int m = matrix.size(), n = matrix[0].size(); bool rowZero = false, colZero = false; for (int i = 0; i < m; ++i) { if (matrix[i][0] == 0) colZero = true; } for (int i = 0; i < n; ++i) { if (matrix[0][i] == 0) rowZero = true; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[i][j] == 0) { matrix[0][j] = 0; matrix[i][0] = 0; } } } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (matrix[0][j] == 0 || matrix[i][0] == 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; } } };
以上就是“C++如何实现矩阵赋零”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注创新互联行业资讯频道。
网站题目:C++如何实现矩阵赋零
分享网址:https://www.cdcxhl.com/article8/gipdip.html
成都网站建设公司_创新互联,为您提供网站改版、品牌网站制作、响应式网站、品牌网站建设、外贸建站、微信公众号
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联