微软专访：转变矩阵 [英] Microsoft Interview: transforming a matrix
问题描述
鉴于大小n×m个的矩阵充满了0和1的
例如：
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
如果矩阵有1个在（I，J），填补了j列和行我与1的
即，我们得到：
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
所需的复杂性：O（N * M）的时间和O（1）空间
请注意：你不能只是'0'任何存储或'1'矩阵中的条目
以上是微软的面试问题。
我现在想了两个小时。我有一些线索，但不能进行了。
确定。这个问题的第一个重要部分是即使使用简单的暴力方式，它不能被轻易解决。
如果我只用两个循环遍历矩阵中的每一个细胞，改变按行和列，也不能这样做的结果矩阵应根据原点矩阵。
例如，如果我看到 A [0] [0] == 1 ，我不能改变 0行和 0列所有 1 ，因为这会影响到第1行为行1 没有0最初。
第二件事我注意到的是，如果行研究只包含 0 和列<$ C $ ç> C 只包含 0 ，然后 A [R] [C] 必须是 0 ;对于这是不是在此模式中任何其它位置应该是 1 。
然后另外一个问题来了，如果我找到了这样的行和列，我怎么可以标记根据电池 A [R] [C] 为特别因为它已经是0。
我的直觉是，我应该用某种位运算的这一点。或满足所要求的复杂性，我必须做一些像之后我照顾的[I] [J]，我应该再着手处理A [1 + 1] [D + 1]而不是扫描逐行或逐列，。
即使是蛮力，不考虑时间复杂度，我不能与其他条件解决这个问题。
任何一个有线索？
解决方案：Java版本
@ JA $ P $小便已经回答了这个问题，他/她的回答是聪明的和正确的。他的code是在Python，现在我给的Java版本。积分都去@ JA $ P $小便
公共类MatrixTransformer {
私人INT [] []一个;
私人诠释米;
私人诠释N;
公共MatrixTransformer（INT [] [] _a，INT _m，诠释_n）{
A = _a;
M = _M;
N = _n;
}
私人诠释scanRow（int i）以{
INT allZero = 0;
为（中间体K = 0; K＆n种; k ++）
如果（A [1] [k]的== 1）{
allZero = 1;
打破;
}
返回allZero;
}
私人诠释scanColumn（诠释J）{
INT allZero = 0;
对于（INT K = 0; K＆其中，M; k ++）
若（a [k]的[J] == 1）{
allZero = 1;
打破;
}
返回allZero;
}
私人无效setRowToAllOnes（int i）以{
为（中间体K = 0; K＆n种; k ++）
一个[I] [K] = 1;
}
私人无效setColToAllOnes（诠释J）{
对于（INT K = 0; K＆其中，M; k ++）
A [k]的[J] = 1;
}
//＃我们要使用的第一个行和列
//＃矩阵存储行和列的扫描值的，
//＃但是我们需要辅助存储，处理重叠
// FIRSTROW = scanRow（0）
// firstCol = scanCol（0）
//
//＃扫描第一排每列，结果存储 - O（MN）工作
公共无效变换（）{
INT FIRSTROW = scanRow（0）;
INT firstCol = scanColumn（0）;
为（中间体K = 0; K＆n种; k ++）{
一个[0] [k]的= scanColumn（k）的;
}
//现在0行告诉我们每一列是否是全零或不
//这也是正确的输出，如果行0含有1原
对于（INT K = 0; K＆其中，M; k ++）{
一个[k]的[0] = scanRow（k）的;
}
一个[0] [0] = firstCol |第一排;
的for（int i = 1; I＆LT;米;我++）
为（诠释J = 1; J＆n种; J ++）
A [1] [J] = A [0] [J]。| A [1] [0];
如果（FIRSTROW == 1）{
setRowToAllOnes（0）;
}
如果（firstCol == 1）
setColToAllOnes（0）;
}
@覆盖
公共字符串的toString（）{
StringBuilder的SB =新的StringBuilder（）;
的for（int i = 0; I＆LT;米;我++）{
为（诠释J = 0; J＆n种; J ++）{
sb.append（A [1] [j]的+，）;
}
sb.append（\ N）;
}
返回sb.toString（）;
}
/ **
* @参数ARGS
* /
公共静态无效的主要（字串[] args）{
INT [] []一个= {{1，1，0，1，0}，{0，0，0，0，0}，{0，1，0，0，0}，{1，0,1 ，1，0}};
MatrixTransformer公吨=新MatrixTransformer（一个，4，5）;
mt.transform（）;
的System.out.println（MT）;
}
}
下面是使用2个额外的布尔 S吸的蟒蛇伪code的解决方案。我认为这是更清晰，比我所能做的英语。
高清scanRow（一）：
返回0，如果行i为全零，否则1
高清scanColumn（J）：
返回0，如果山坳j为全零，否则1
＃我们将要使用的第一个行和列
＃矩阵存储行和列的扫描值的，
＃但是我们需要辅助存储，处理重叠
FIRSTROW = scanRow（0）
firstCol = scanCol（0）
＃扫描第一排每列，结果存储 - O（MN）工作
用于COL的范围（1，N）：
矩阵[0，列] = scanColumn（COL）
＃现在0行告诉我们每一列是否是全零或不
＃这也是正确的输出，如果行0含有1原
＃做同样的行成列的0 - O（MN）工作
对于行中的范围（1，米）：
矩阵[行，0] = scanRow（行）
矩阵[0,0] = FIRSTROW或firstCol
＃现在处理的其余值 - O（MN）工作
对于行中的范围（1，米）：
用于COL的范围（1，N）：
矩阵[行，列] =矩阵[0，列]或矩阵[行，0]
＃3 O（MN）通过！
＃回去收拾行0和列0
如果FIRSTROW：
＃集行0为全
如果firstCol：
＃设置COL 0为全
Given a matrix of size n x m filled with 0's and 1's
e.g.:
1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0
if the matrix has 1 at (i,j), fill the column j and row i with 1's
i.e., we get:
1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
Required complexity: O(n*m) time and O(1) space
NOTE: you are not allowed to store anything except '0' or '1' in the matrix entries
Above is a Microsoft Interview Question.
I thought for two hours now. I have some clues but can't proceed any more.
Ok. The first important part of this question is that Even using a straight forward brute-force way, it can't be easily solved.
If I just use two loops to iterate through every cell in the matrix, and change the according row and column, it can't be done as the resulting matrix should be based on the origin matrix.
For example, if I see a[0][0] == 1, I can't change row 0 and column 0 all to 1, because that will affect row 1 as row 1 doesn't have 0 originally.
The second thing I noticed is that if a row r contains only 0 and a column c contains only 0, then a[r][c] must be 0; for any other position which is not in this pattern should be 1.
Then another question comes, if I find such a row and column, how can I mark the according cell a[r][c] as special as it already is 0.
My intuitive is that I should use some kind of bit operations on this. Or to meet the required complexity, I have to do something like After I take care of a[i][j], I should then proceed to deal with a[i+1][j+1], instead of scan row by row or column by column.
Even for brute-force without considering time complexity, I can't solve it with the other conditions.
Any one has a clue?
Solution: Java version
@japreiss has answered this question, and his/her answer is smart and correct. His code is in Python, and now I give the Java version. Credits all go to @japreiss
public class MatrixTransformer {
private int[][] a;
private int m;
private int n;
public MatrixTransformer(int[][] _a, int _m, int _n) {
a = _a;
m = _m;
n = _n;
}
private int scanRow(int i) {
int allZero = 0;
for(int k = 0;k < n;k++)
if (a[i][k] == 1) {
allZero = 1;
break;
}
return allZero;
}
private int scanColumn(int j) {
int allZero = 0;
for(int k = 0;k < m;k++)
if (a[k][j] == 1) {
allZero = 1;
break;
}
return allZero;
}
private void setRowToAllOnes(int i) {
for(int k = 0; k < n;k++)
a[i][k] = 1;
}
private void setColToAllOnes(int j) {
for(int k = 0; k < m;k++)
a[k][j] = 1;
}
// # we're going to use the first row and column
// # of the matrix to store row and column scan values,
// # but we need aux storage to deal with the overlap
// firstRow = scanRow(0)
// firstCol = scanCol(0)
//
// # scan each column and store result in 1st row - O(mn) work
public void transform() {
int firstRow = scanRow(0);
int firstCol = scanColumn(0);
for(int k = 0;k < n;k++) {
a[0][k] = scanColumn(k);
}
// now row 0 tells us whether each column is all zeroes or not
// it's also the correct output unless row 0 contained a 1 originally
for(int k = 0;k < m;k++) {
a[k][0] = scanRow(k);
}
a[0][0] = firstCol | firstRow;
for (int i = 1;i < m;i++)
for(int j = 1;j < n;j++)
a[i][j] = a[0][j] | a[i][0];
if (firstRow == 1) {
setRowToAllOnes(0);
}
if (firstCol == 1)
setColToAllOnes(0);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i< m;i++) {
for(int j = 0;j < n;j++) {
sb.append(a[i][j] + ", ");
}
sb.append("\n");
}
return sb.toString();
}
/**
* @param args
*/
public static void main(String[] args) {
int[][] a = {{1, 1, 0, 1, 0}, {0, 0, 0, 0, 0},{0, 1, 0, 0, 0},{1, 0, 1, 1, 0}};
MatrixTransformer mt = new MatrixTransformer(a, 4, 5);
mt.transform();
System.out.println(mt);
}
}
Here is a solution in python pseudocode that uses 2 extra bools of storage. I think it is more clear than I could do in English.
def scanRow(i):
return 0 if row i is all zeroes, else 1
def scanColumn(j):
return 0 if col j is all zeroes, else 1
# we're going to use the first row and column
# of the matrix to store row and column scan values,
# but we need aux storage to deal with the overlap
firstRow = scanRow(0)
firstCol = scanCol(0)
# scan each column and store result in 1st row - O(mn) work
for col in range(1, n):
matrix[0, col] = scanColumn(col)
# now row 0 tells us whether each column is all zeroes or not
# it's also the correct output unless row 0 contained a 1 originally
# do the same for rows into column 0 - O(mn) work
for row in range(1, m):
matrix[row, 0] = scanRow(row)
matrix[0,0] = firstRow or firstCol
# now deal with the rest of the values - O(mn) work
for row in range(1, m):
for col in range(1, n):
matrix[row, col] = matrix[0, col] or matrix[row, 0]
# 3 O(mn) passes!
# go back and fix row 0 and column 0
if firstRow:
# set row 0 to all ones
if firstCol:
# set col 0 to all ones
这篇关于微软专访：转变矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
