找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1662|回复: 3
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Set Matrix Zeroes】-【刷题第一弹】

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 10-8-2014 07:29 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 TeamEditor 于 10-31-2014 07:38 PM 编辑

快速通道:

题目:

建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
            汇总贴 传送门
=================================

本帖被以下淘专辑推荐:

18

主题

9

精华

522

积分

超级会员

Rank: 4

积分
522
发表于 10-31-2014 07:22 PM | 显示全部楼层
思路:首先判断第一行和第一列是否有零,然后利用第一行或者第一列统计每行或者每列是否有零
复杂度: 时间O(m*n), 空间O(1)
  1. class Solution {
  2. public:
  3.     void setZeroes(vector<vector<int> > &matrix) {
  4.         if(matrix.size() == 0)
  5.             return;
  6.             
  7.        const size_t m = matrix.size();
  8.        const size_t n = matrix[0].size();
  9.        bool row_has_zero = false; // 第一行是否存在0
  10.        bool col_has_zero = false; // 第一列是否存在0
  11.       
  12.        for (size_t i = 0; i < n; i++)
  13.             if (matrix[0][i] == 0) {
  14.                 row_has_zero = true;
  15.                 break;
  16.                 }
  17.       
  18.        for (size_t i = 0; i < m; i++)
  19.             if (matrix[i][0] == 0) {
  20.                 col_has_zero = true;
  21.                 break;
  22.                 }
  23.                
  24.        for (size_t i = 1; i < m; i++)
  25.             for (size_t j = 1; j < n; j++)
  26.                 if (matrix[i][j] == 0) {
  27.                     matrix[0][j] = 0;
  28.                     matrix[i][0] = 0;
  29.                     }
  30.         
  31.         for (size_t i = 1; i < m; i++)
  32.                 for (size_t j = 1; j < n; j++)
  33.                     if (matrix[i][0] == 0 || matrix[0][j] == 0)
  34.                         matrix[i][j] = 0;
  35.                         
  36.         if (row_has_zero)
  37.                 for (size_t i = 0; i < n; i++)
  38.                     matrix[0][i] = 0;
  39.                     
  40.         if (col_has_zero)
  41.                 for (size_t i = 0; i < m; i++)
  42.                     matrix[i][0] = 0;
  43.       }
  44. };
复制代码
回复 支持 反对

使用道具 举报

18

主题

9

精华

522

积分

超级会员

Rank: 4

积分
522
发表于 10-31-2014 07:26 PM | 显示全部楼层
本帖最后由 dolremi 于 11-1-2014 12:44 PM 编辑

思路: 利用bitset来做,可惜Oj没法识别bitset
复杂度跟之前一样
  1. #include <bitset>
  2. class Solution {
  3. public:
  4.     void setZeroes(vector<vector<int> > &matrix) {
  5.         if(matrix.empty()){
  6.           return;
  7.          }
  8.         int row=matrix.size();   
  9.         int col=matrix[0].size();
  10.         
  11.         bitset<row> rowflag;
  12.         bitset<col> colflag;
  13.         for(int i=0; i<row; ++i) {
  14.             for(int j=0; j<col; ++j) {
  15.                 if(matrix[i][j]==0) {
  16.                     rowflag.set(i);
  17.                     colflag.set(j);
  18.                 }
  19.             }
  20.         }        
  21.         for(int i=0; i<row; ++i) {
  22.             for(int j=0; j<col; ++j) {
  23.                 if(rowflag.test(i)||colflag.test(j)) {
  24.                     matrix[i][j]=0;
  25.                 }
  26.             }
  27.         }  
  28.     }
  29. };
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表