给定一个N×N的矩阵,0和1。设置一个包含每一行 0
所有 0
和设置包含每列 0
所有 0
秒。
Given a NxN matrix with 0s and 1s. Set every row that contains a 0
to all 0
s and set every column that contains a 0
to all 0
s.
例如
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
结果
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
一个微软工程师告诉我,有一个解决方案,不涉及额外的内存,只有两个布尔变量和一个传球,所以我在寻找这个问题的答案。
A Microsoft Engineer told me that there is a solution that involves no extra memory, just two boolean variables and one pass, so I'm looking for that answer.
顺便说一句,想象它是一个有点矩阵,因此只需1和0被允许在基质中。
BTW, imagine it is a bit matrix, therefore just 1s and 0s are allow to be in the matrix.
好了,我也累了,因为它是上午03点在这里,但我有一个第一次尝试就地恰好有2次通过矩阵中的每个数字,因此为O (N×N个),它是线性的矩阵的大小。
Ok, so I'm tired as it's 3AM here, but I have a first try inplace with exactly 2 passes on each number in the matrix, so in O(NxN) and it is linear in the size of the matrix.
我用1rst列和第一行作为标记知道哪里是行/ COLS只有1的。然后,有2个变量L和C要记住,如果1rst行/列全部为1也。 所以第一遍设置标记,其余的重置为0。
I use 1rst column and first row as markers to know where are rows/cols with only 1's. Then, there are 2 variables l and c to remember if 1rst row/column are all 1's also. So the first pass sets the markers and resets the rest to 0's.
第二遍集1中的地方被标行列数为1,并复位第一行/列取决于升和c。
The second pass sets 1 in places where rows and cols where marked to be 1, and resets 1st line/col depending on l and c.
我怀疑坚信我一定能在1通来完成在年初广场取决于到底广场。也许我的第2次,可以更加高效......
I doubt strongly that I can be done in 1 pass as squares in the beginning depend on squares in the end. Maybe my 2nd pass can be made more efficient...
import pprint
m = [[1, 0, 1, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 1],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1]]
N = len(m)
### pass 1
# 1 rst line/column
c = 1
for i in range(N):
c &= m[i][0]
l = 1
for i in range(1,N):
l &= m[0][i]
# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
for j in range(1,N):
if m[i][j] == 0:
m[0][j] = 0
m[i][0] = 0
else:
m[i][j] = 0
### pass 2
# if line1 and col1 are ones: it is 1
for i in range(1,N):
for j in range(1,N):
if m[i][0] & m[0][j]:
m[i][j] = 1
# 1rst row and col: reset if 0
if l == 0:
for i in range(N):
m [i][0] = 0
if c == 0:
for j in range(1,N):
m [0][j] = 0
pprint.pprint(m)
上一篇:棘手的谷歌面试问题棘手、问题