一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 968|回复: 7
收起左侧

[CareerCup] CC150 1.7把矩阵元素为0的行和列清空

[复制链接] |试试Instant~ |关注本帖
TonyJang 发表于 2014-8-28 16:46:59 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x



  1. public class Q1_7{

  2. public static void SetZero( int[][] matrix){

  3. boolean [] row= new boolean[ matrix. length ];  //二维矩阵的长度指行数,并且和字符串的长度method不一样,没有()

  4. boolean [] column = new boolean[ matrix[0]. length]; //列数

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

  6. for (int j =0;j <matrix [0].length ;j ++){

  7. if (matrix [i ][j ]==0){
  8. row [i ]= true;
  9. column [j ]= true;
  10. }


  11. }



  12. }


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

  14. for (int j =0;j <matrix [0].length ;j ++){
  15. if (row [i ]||column [j ]){

  16. matrix [i ][j ]=0;

  17. }


  18. }

  19. }


  20. }


  21. public static void main(String[] args){

  22.         int [][] matrix = new int[][]{
  23.                         {1,2,3,4,},
  24.                         {5,6,7,8,},
  25.                         {9,1,2,4},
  26.                         {2,0,4,9}
  27.                      };



  28. SetZero( matrix);
  29. for (int i =0;i <4;i ++){
  30. for (int j =0;j <4;j ++){

  31. System. out.print( matrix[ i][ j]);


  32. }

  33. System. out.println();

  34. }

  35. }


  36. }
复制代码
1)原方法是新建一个M*N的矩阵,所以空间复杂度为O(M*N)=N的平方,第二种开两个数组所以为O(M+N)=O(1),对吗?
关闭
2)时间复杂度?




amorsleeping 发表于 2014-8-28 18:41:56 | 显示全部楼层
本帖最后由 amorsleeping 于 2014-8-28 18:59 编辑

空间:O(M+N)时间:找0的时候扫描一遍原数组O(MN),设0的时候再扫描一遍原数组O(MN),所以还是O(MN)
回复 支持 反对

使用道具 举报

jxzhuge12 发表于 2014-8-28 19:07:14 | 显示全部楼层
本帖最后由 jxzhuge12 于 2014-8-28 19:12 编辑

空间O(1)
时间O(MN)
设flag1为第0行是否有0,若有,设为1,若无,设为0
设flag2为第0列是否有0,若有,设为1,若无,设为0
从第一行第一列开始遍历矩阵,若找到0,假设在第m行第n列,则将第0列第m行设为0,将第0行第n列设为0
从第一列开始遍历第0行,将0所在位置的列全部置为0
从第一行开始遍历第0列,将0所在位置的行全部置为0
若flag1为1,则将第0行全部置为0
若flag2为1,则将第0列全部置为0
  1. class Solution {
  2. public:
  3.         void setZeroes(vector<vector<int>> &matrix) {
  4.                 int m = matrix.size();
  5.                 int n = matrix[0].size();
  6.                 int flag1 = 0;
  7.                 int flag2 = 0;
  8.                 for (int j = 0; j < n; j++){
  9.                         if (matrix.at(0)[j] == 0){
  10.                                 flag1 = 1;
  11.                         }
  12.                 }
  13.                 for (int i = 0; i < m; i++){
  14.                         if (matrix.at(i)[0] == 0){
  15.                                 flag2 = 1;
  16.                         }
  17.                 }
  18.                 for (int i = 1; i < m; i++){
  19.                         for (int j = 1; j < n; j++){
  20.                                 if (matrix.at(i)[j] == 0){
  21.                                         matrix.at(0)[j] = 0;
  22.                                         matrix.at(i)[0] = 0;
  23.                                 }
  24.                         }
  25.                 }
  26.                 for (int i = 1; i < m; i++){
  27.                         if (matrix.at(i)[0] == 0){
  28.                                 for (int j = 1; j < n; j++){
  29.                                         matrix.at(i)[j] = 0;
  30.                                 }
  31.                         }
  32.                 }
  33.                 for (int j = 1; j < n; j++){
  34.                         if (matrix.at(0)[j] == 0){
  35.                                 for (int i = 1; i < m; i++){
  36.                                         matrix.at(i)[j] = 0;
  37.                                 }
  38.                         }
  39.                 }
  40.                 if (flag1 == 1){
  41.                         for (int j = 0; j < n; j++){
  42.                                 matrix.at(0)[j] = 0;
  43.                         }
  44.                 }
  45.                 if (flag2 == 1){
  46.                         for (int i = 0; i < m; i++){
  47.                                 matrix.at(i)[0] = 0;
  48.                         }
  49.                 }
  50.         }
  51. };
复制代码
回复 支持 反对

使用道具 举报

jxzhuge12 发表于 2014-8-28 19:07:50 | 显示全部楼层
O(M+N)谁跟你说等于O(1)的。。
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-8-28 21:26:15 | 显示全部楼层
jxzhuge12 发表于 2014-8-28 19:07
O(M+N)谁跟你说等于O(1)的。。

俺猜的,O(M+N)=O(N)是么?
回复 支持 反对

使用道具 举报

jxzhuge12 发表于 2014-8-28 21:28:16 | 显示全部楼层
TonyJang 发表于 2014-8-28 21:26
俺猜的,O(M+N)=O(N)是么?

恩,,对的,,,
回复 支持 反对

使用道具 举报

 楼主| TonyJang 发表于 2014-8-28 21:38:44 | 显示全部楼层
jxzhuge12 发表于 2014-8-28 21:28
恩,,对的,,,

soga,谢谢大牛指导,你的solution比较牛啊
回复 支持 反对

使用道具 举报

jxzhuge12 发表于 2014-8-29 10:08:55 | 显示全部楼层
TonyJang 发表于 2014-8-28 21:38
soga,谢谢大牛指导,你的solution比较牛啊

没有啦,也是想了很久才想出来的
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 04:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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