H*M
发帖数: 1268 | 1 agiven n by n matrix( elements are either 0 or 1)
find out if there exist a row i and column j such that
1) all elements of row i are zeros
2) all elements of column j are 1s
3)(i,j) entry can be either 0 or 1
my thinking is:
sum each row and each column
if sumRow[i] > 1 mark it false
if sumCol[i]
also for those rows and cols,if they are not marked false, record the 1 posi
tions for row and 0 positions for col when doing sum.
for those cols and rows that are not marked false |
m*****f
发帖数: 1243 | 2 to get the row, multiply matrix with a nx1 vector with all 1.
to get the column, do the same with its transpose matrix
the all-1/0-row/columns are recorded as n/0 in the result vector |
H*M
发帖数: 1268 | 3 没看懂.能写清楚点不?
结论是什么?可以有更有效的方法?
【在 m*****f 的大作中提到】
: to get the row, multiply matrix with a nx1 vector with all 1.
: to get the column, do the same with its transpose matrix
: the all-1/0-row/columns are recorded as n/0 in the result vector
|
m********0
发帖数: 2717 | 4 you forgot the complexity of
matrix multiplication itself.
in this case, still O(n^2).
and '+' is faster than '*' in general.
So what you offer is a worse solution.
【在 m*****f 的大作中提到】
: to get the row, multiply matrix with a nx1 vector with all 1.
: to get the column, do the same with its transpose matrix
: the all-1/0-row/columns are recorded as n/0 in the result vector
|
l***i
发帖数: 632 | 5
I don't understand 3)... Isn't it already an assumption that the matrix is
binary?
posi
【在 H*M 的大作中提到】
: agiven n by n matrix( elements are either 0 or 1)
: find out if there exist a row i and column j such that
: 1) all elements of row i are zeros
: 2) all elements of column j are 1s
: 3)(i,j) entry can be either 0 or 1
: my thinking is:
: sum each row and each column
: if sumRow[i] > 1 mark it false
: if sumCol[i] : also for those rows and cols,if they are not marked false, record the 1 posi
|
m*****f
发帖数: 1243 | 6 虽然是矩阵乘法， 可是计算的时候用的都是加法阿...
本来就是O(n^2)， 要判断某行某列是否都是1/0, 起码要scan整个matrix一遍罢，
不太可能少于O(n^2).
【在 m********0 的大作中提到】
: you forgot the complexity of
: matrix multiplication itself.
: in this case, still O(n^2).
: and '+' is faster than '*' in general.
: So what you offer is a worse solution.
|
