一亩三分地论坛

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

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

[CareerCup] 【第四轮】3.30 -4.5 Career Cup 1.7

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-3-30 10:35:27 | 显示全部楼层 |阅读模式

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

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

x
1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row
and column are set to 0.

请参加活动的童鞋跟帖回复自己的解法,回复请参考以下格式:

解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改

Pony_s 发表于 2015-3-30 17:41:50 | 显示全部楼层
好像很不错的活动,规则是什么?
回复 支持 反对

使用道具 举报

 楼主| pure0909 发表于 2015-3-31 01:22:06 | 显示全部楼层
Pony_s 发表于 2015-3-30 17:41
好像很不错的活动,规则是什么?

详情请见本版置顶帖~~
回复 支持 反对

使用道具 举报

kateheart 发表于 2015-3-31 10:45:55 | 显示全部楼层
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

import java.util.Set;
import java.util.HashSet;
import java.awt.Point;

class SetZero {
  public static void main(String[] args){
    int[][] T = {{0,1,1,1,1}, {2,2,2,2,2}, {3,3,3,3,0}};
    print(T);
    Set<Point> S = findZero(T);
    System.out.println(S);
    solve(T);
    print(T);
  }

  public static void print(int[][] matrix){
    int w = matrix[0].length, h = matrix.length;
    for (int y = 0; y < h; ++y) {
      for (int x = 0; x < w; ++x) {
        System.out.print(matrix[y][x]);
      }
      System.out.print("\n");
    }
  }
  //given a point, set its row and column to zeros
  public static void setZero(int[][] matrix, int x0, int y0){
    int h = matrix.length;
    int w = matrix[0].length;
    for(int x = 0; x < w; ++x){
      matrix[y0][x] = 0;
    }
    for(int y = 0; y < h; ++y){
      matrix[y][x0] = 0;
    }
  }
  public static Set<Point> findZero(int[][] matrix){
     int w = matrix[0].length, h = matrix.length;
     Set<Point> zeros = new HashSet<Point>();
     for(int y = 0; y < h; ++y){
        for(int x =0; x < w; ++x){
          if(matrix[y][x] == 0){
            zeros.add(new Point(x,y));
          }
        }
     }
     return zeros;
  }

  public static void solve(int[][] matrix){
    for(Point s: findZero(matrix)){
      setZero(matrix,s.x,s.y);
    }
  };
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-1 12:47:19 | 显示全部楼层
  解题思路】
Using two loops to record the zero positions and then set values
Using two set to store the zeroRow and zeroCol
【时间复杂度】
O(N^2)
【空间复杂度】
O(N)
【gist link]
https://gist.github.com/zhangjiang2013/bd5f3102776e54b97622
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

laonong15 发表于 2015-4-1 23:14:02 | 显示全部楼层
【解题思路】
we only need know  which row and  column to be set to  0
  so  we need  set two boolean array to  mark the    rows and columns should be set to  0
【时间复杂度】
O(N*M)
【空间复杂度】
O(N+M)
【gist link]
https://gist.github.com/michaelniu/cbeb9826a8c8d040fe9e

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-4-2 03:45:52 | 显示全部楼层
//Solution1
// 如果矩阵如果有元素为0,就把对应的行和列上面的元素都置为0。
// 这里最大的问题就是我们遇到0的时候不能直接把矩阵的行列在当前矩阵直接置0,
// 否则后面还没访问到的会被当成原来是0,最后会把很多不该置0的行列都置0了。
// 一个直接的想法是备份一个矩阵,然后在备份矩阵上判断,
// 在原矩阵上置0,这样当然是可以的,不过空间复杂度是O(m*n),不是很理想。

//Solution2
// 我们看到其实判断某一项是不是0只要看它对应的行或者列应不应该置0就可以,
// 所以我们可以维护一个行和列的布尔数组,然后扫描一遍矩阵记录那一行或者列是不是应该置0即可,
// 后面赋值是一个常量时间的判断。这种方法的空间复杂度是O(m+n)

//Solution3
// 我们考虑使用第一行和第一列来记录上面所说的行和列的置0情况,
// 这里问题是那么第一行和第一列自己怎么办?想要记录它们自己是否要置0,
// 只需要两个变量(一个是第一行,一个是第一列)就可以了。
//然后就是第一行和第一列,如果要置0,就把它的值赋成0(反正它最终也该是0,无论第一行或者第一列有没有0),否则保留原值。
// 然后根据第一行和第一列的记录对其他元素进行置0。最后再根据前面的两个标记来确定是不是要把第一行和第一列置0就可以了。
// 这样的做法只需要两个额外变量,所以空间复杂度是O(1)。
// 时间上来说上面三种方法都是一样的,需要进行两次扫描,
// 一次确定行列置0情况,一次对矩阵进行实际的置0操作,所以总的时间复杂度是O(m*n)

https://gist.github.com/JamesJi9277/aee07981770df9840054

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

A30041839 发表于 2015-4-2 16:27:00 | 显示全部楼层
[solution]
use two flags to indicate if the first row & col need to be reset. use the first row&col to record if the corresponding row or col need to be reset. This reduces the space complexity to O(1)
[time]
O(mn)
[space]
O(1)
[gist]
https://gist.github.com/A30041839/af34e4ffa18b39c57a16

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

chongtianzs 发表于 2015-4-3 12:44:46 | 显示全部楼层
[solution]
用两个变量来记录第一行和第一列是否需要置零;用第一行和第一列来记录每一行和每一列是否需要置零;扫两边矩阵,第一遍用来记录哪一行需要置零,第二遍用来置零。
[time]
O(mn)
[space]
O(1)
[gist]
https://gist.github.com/chongtianzs/a7eb6914e0fb21e8e054

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-4-4 12:50:29 | 显示全部楼层
【解题思路】
建立两个新数组,一个记录需要置0的行,一个记录需要置0的列,扫两遍矩阵,第一次标记置零的列和行,第二次执行置零操作
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/alikewmk ... -1-7-crosszero-java

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-5 06:15:36 | 显示全部楼层
本帖最后由 slaink 于 2015-4-5 06:18 编辑

解题思路】
// If martix[j] = 0, then martix[] = 0 and matrix[][j] = 0        
// We construct two array indicators to log if a row/col should be set to zero
【时间复杂度】
* Time complexity: O(m*n)
【空间复杂度】
* Space complexity: O(m+n)
【gist link] https://github.com/bxshi/intervi ... I5/1_7_set_zero.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享) https://github.com/bxshi/intervi ... c/test/1_7_test.cpp


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

daphne_ying 发表于 2015-4-6 04:21:37 | 显示全部楼层
[solution]
1. use two bool arrays, one to indicate whether a row should be set to zero, another to indicate whether a col should be set to zero.
2. first scan of the matrix to update the two bool arrays.
3. second scan of the matrix to set the correspond elements.
[time]
O(mn)
[space]
O(m+n)
[gist]
https://gist.github.com/kelly-us/9d0af336171822f9c17e

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2015-4-6 07:03:46 | 显示全部楼层
【解题思路】
* First, we at least need two loops, one for finding out the rows and columns containing 0,
* the other one to set 0. We cannot do it in one loop, because it will influence result.
* We set the row and column which contain 0, true.
* Then in the next loop, if row or column is true, we set it 0.
*
* Note: "or" is very important here, think about it. I used three loops initially, which is not most efficient.
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/leonw007/47cf3244fea404e21562
【test case】included in the link above

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sevenwonder 发表于 2015-4-6 11:06:49 | 显示全部楼层
【解题思路】
可以开一个行数组row和列数组col,当元素a[j]等于0时, 就把row和col[j]置为true。第二次遍历矩阵时,当某个元素对应的行row 或列col[j]被设置为true,说明该元素在需要被置0的行或列上,因此将它置0。
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/songpu2015617/46b8ba53f41adb40560a

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Godbless 发表于 2015-4-6 13:25:58 | 显示全部楼层
【解题思路】Two passes: First pass to find the row indexes and column indexes which contain 0 element. Second pass to set the element which lies either in the row indexes or column indexes to zero.
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link]
https://github.com/StephenWeiXu/ ... blob/master/1_7.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/StephenWeiXu/ ... blob/master/1_7.cpp

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

beer 发表于 2015-4-7 01:45:17 | 显示全部楼层
【解题思路】
Tips:
* Use two array to mark which row and which col should be reset to zero perspectively.
* Use the first row and column to mark which row and col should be reset to zero perspectively.
【时间复杂度】1&2. O(M*N)
【空间复杂度】1. O(M+N) 2.O(1)
【gist link】https://github.com/drinkbeer/Cod ... /src/CC150_1_7.java
【test case】

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

yaooffer 发表于 2015-9-13 06:04:21 | 显示全部楼层
【gist link】github.com/Etherque/Career-Cup/blob/master/setZeros.java"
Time Complexity O(m x n)
Space O(1)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 05:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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