一亩三分地论坛

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

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

[CareerCup] 【第三轮】6.16-6.22 CareerCup 1.7

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-6-15 23:21:42 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去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】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


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

zhenzhenanan 发表于 2014-6-18 00:25:05 | 显示全部楼层
本帖最后由 zhenzhenanan 于 2014-6-18 00:41 编辑

【解题思路】
LeetCode原题。
1. 设两个bool变量,一个用来描述第行是否有零;另一个用来描述第一列是否有零。
2. 遍历整个matrix,如果某一个元素是0,则把它所在的行的第一个元素设为0,并把它所在的列的第一个元素设为0。
3. 根据第一行和第一列里面的0,把对应的行和列都设为0。
4. 根据第一步中的两个变量,把第一行和第一列设为0。
【时间复杂度】
O(mn)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-1_7-cc
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 1 反对 0

使用道具 举报

qianhuang 发表于 2014-6-16 10:21:05 | 显示全部楼层
【解题思路】
Assume this problem want us to set 0 according the initial matrix.
Simplest method: create a MxN matrix to store where 0 appear, then according it, we can set the row and column. Additional space is O(MN), runtime is O(MN), since we must scan the whole matrix, we cannot optimize the runtime.
To optimize the space, the aim is to set row and column, so we only need to store whether there are 0 in the row/column, thus the space is O(M+N).
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/qianhuang/b93ec80f0ad06cfeb0fc
回复 支持 反对

使用道具 举报

habina 发表于 2014-6-16 17:06:58 | 显示全部楼层
【解题思路】
  Collect all indices that elements are zero
  Set element to zero where the element's horizontal or vertical index appears in the collection
【时间复杂度】
  O(NM)
【空间复杂度】
  O(1)
【gist link】
  https://gist.github.com/habina/7cab9ec45a5bf766cce3
回复 支持 反对

使用道具 举报

readman 发表于 2014-6-16 23:34:14 | 显示全部楼层

【解题思路】
same to the one on book
【时间复杂度】
N^2
【空间复杂度】
N
【gist link】
https://gist.github.com/gaoyike/bf57c6e80674c04d44b2
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-6-17 11:56:59 | 显示全部楼层
【解题思路】
same to the one on book
【时间复杂度】
O(mn)
【空间复杂度】
O(m+n)
【gist link】
https://gist.github.com/JoyceeLee/19a09295137e1b537987
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-6-18 08:21:17 | 显示全部楼层
【解题思路】
two boolean arrays, one to tag the row which has 0s, and another to tag the column which has 0s. second pass is to set matrix[j] = 0 if row or column has zeros.
【时间复杂度】
O(M*N)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/iwilbert/9a6463330ddf8ac34b61
回复 支持 反对

使用道具 举报

chouclee 发表于 2014-6-18 11:42:52 | 显示全部楼层
【解题思路】Use two extra boolean arrays to record which rows and cols should be set to 0.
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/chouclee/1ba6e45c932413c8b401
回复 支持 反对

使用道具 举报

jing0328 发表于 2014-6-18 22:53:25 | 显示全部楼层
【解题思路】find rows and columns where zeros lie, then set zeros to corresponding rows and columns
【时间复杂度】O(mn)
【空间复杂度】O(n)
【gist link】https://gist.github.com/startupjing/06c91feafb652793cfe8
回复 支持 反对

使用道具 举报

小柯西 发表于 2014-6-19 00:55:08 | 显示全部楼层
【解题思路】Same to previous posters.
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/849a31e739c234a7555e.git
回复 支持 反对

使用道具 举报

asdw3276 发表于 2014-6-19 01:23:27 | 显示全部楼层
【解题思路】两次遍历,第一次记录flag,第二次根据flag设置矩阵
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/asdw3276/fda81d69ab0bc1b0bb3b
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-6-19 07:32:49 | 显示全部楼层
【解题思路】
two boolean arrays, one to tag the row which has 0s, and another to tag the column which has 0s. second pass is to set matrix[j] = 0 if row or column has zeros.
【时间复杂度】
O(M*N)
【空间复杂度】
O(M+N)
【gist link】https://gist.github.com/hilda8519/2d76dc3a2bb10751c167
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-6-19 09:17:35 | 显示全部楼层
【解题思路】
use the first row and first column to record which row or column should be zero.   need some pre-process to record whether the first row or the first column have any zeroes.
【时间复杂度】
O(M*N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/jyhjuzi/af7a2e0a10787a06fb8b
回复 支持 反对

使用道具 举报

grassgigi 发表于 2014-6-21 10:32:25 | 显示全部楼层
【解题思路】
Keep two status sets tracking whether a row or column contains zero, and do in place replacement of zeros according to status sets.

【时间复杂度】
O(MN) for go through matrix twice
was stupidly trying to find some O(Max(M,N)) algo for an hour...
【空间复杂度】
O(M+N)

【gist link】
https://gist.github.com/chrislukkk/fd880801c2c56e28e2dc
回复 支持 反对

使用道具 举报

Tsien 发表于 2014-6-21 23:27:13 | 显示全部楼层
【解题思路】
a routine way:
use two sets to record where the element is zero,
then clear those rows and columns
【时间复杂度】
O(MN)
【空间复杂度】
O(M+N)
【gist link】
https://gist.github.com/Tsien/a39a2edf6c4535eba329
回复 支持 反对

使用道具 举报

七00夜 发表于 2014-6-21 23:53:19 | 显示全部楼层
【解题思路】
随机生成一个(0~9)的二维数组(M*N),并复制该数组,遍历原数组,找到0的下标i , j,并将新数组对应的i行和j列置0。
【时间复杂度】

【空间复杂度】

【gist link】
https://gist.github.com/ba245a6dd03dde387e60.git
回复 支持 反对

使用道具 举报

aloncgo 发表于 2014-6-22 00:41:24 | 显示全部楼层
【解题思路】两次遍历,第一次记录零所在的行列,第二次置零
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/weazord/56924e3c39d5b898251



Test 1
Original:
1        0       
0        1       

Zeroes Set:
0        0       
0        0       

Test 2
Original
1        2        0        4        5       
6        7        8        9        10       
11        12        13        14        15       
16        17        18        19        20       

Zeroes Set:
0        0        0        0        0       
6        7        0        9        10       
11        12        0        14        15       
16        17        0        19        20       

Test 3
Original
1        2        3        4        5        6       
7        8        0        10        11        12       
13        14        15        16        0        18       
19        20        21        22        23        24       
25        26        27        28        29        30       

Zeroes Set:
1        2        0        4        0        6       
0        0        0        0        0        0       
0        0        0        0        0        0       
19        20        0        22        0        24       
25        26        0        28        0        30       



回复 支持 反对

使用道具 举报

bearkino 发表于 2014-6-22 06:04:15 | 显示全部楼层
【解题思路】
首先,先检查第一行和第一列,有0的话标记为true,然后检查matrix里面的元素,有0的话就在第一行或者第一列标记0. 然后set zero的时候,先检查第一行或者第一列是否有0,有的话就把对应的行列归零;然后检查是否有true, 有的话再把第一行或者第一列归零。结束。
【时间复杂度】
O(MN)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/UncleGarden/64c7132968c6c205605a
回复 支持 反对

使用道具 举报

头像被屏蔽
serolins 发表于 2014-6-22 10:49:02 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-6-22 11:38:13 | 显示全部楼层

【解题思路】Traverse the matrix, find the zero row and column, then set the columns and rows' elements as 0
【时间复杂度】O(MN)
【空间复杂度】O(M+N)
【gist link】https://gist.github.com/bitcpf/91139d9c1a058eee5258
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 07:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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