算法以修改的矩阵和设定列和行到零 [英] Algorithm to modify a matrix and set columns and rows to zero
问题描述
这在技术上是一个code挑战。 有人问我一个有趣的问题，在接受记者采访时，我希望一些见解，因为我可以用了哦，来了最好的答案（2N ^ 2） - N平方的类别，但仍然pretty的多少蛮力。
让我们假设你有一个矩阵的并购由N个尺寸（数组的数组（INT [] []））
1 2 4 3 1
0 5 3 7 7
5 8 9 2 8
6 7 0 8 9
如果单元格中包含一个零，然后设置整行和列为零。
使得结果：
0 2 0 3 1
0 0 0 0 0
0 8 0 2 8
0 0 0 0 0
什么是做到这一点的最快和/或最佳方式是什么？
我自己的答案是遍历数组的整个数组，跟踪的行和列来零，然后零出来。
公共无效zeroOut（INT [] [] myArray的）{
ArrayList的＆LT;整数GT; rowsToZero =新....
ArrayList的＆LT;整数GT; columnsToZero =新....
的for（int i = 0; I＆LT; myArray.length;我++）{//记录下哪些行和列将被清零
对于（INT J = 0; J＆LT; myArray的[I] .length;我++）{
如果（myarray的[I] [J] == 0）{
如果（rowsToZero.contains（ⅰ）！）rowsToZero.add（ⅰ）;
如果（columnsToZero.contains（J）！）columnsToZero.add（J）;
}
}
}
对于（INT行：行）{//现在零的行
myArray的[行] = INT [myArray.length]
}
的for（int i = 0; I＆LT; myArray.length;我++）{
对于（INT列：列）{//现在零列
myArray的[I] [列] = 0;
}
}
}
有没有更好的算法？有没有更好的数据结构来重新present这个矩阵？
似乎没有人真正想出了一个显著更快/更好的算法，到目前为止，所以这一块似乎是它。感谢您的输入大家。
公共无效zeroOut（INT [] [] myArray的）{
ArrayList的＆LT;整数GT; rowsToZero =新....
ArrayList的＆LT;整数GT; columnsToZero =新....
的for（int i = 0; I＆LT; myArray.length;我++）{//记录下哪些行和列将被清零
对于（INT J = 0; J＆LT; myArray的[I] .length;我++）{
如果（myarray的[I] [J] == 0）{
如果（rowsToZero.contains（ⅰ）！）rowsToZero.add（ⅰ）;
如果（columnsToZero.contains（J）！）columnsToZero.add（J）;
}
}
}
对于（INT行：行）{//现在零的行
myArray的[行] = INT [myArray.length]
}
的for（int i = 0; I＆LT; myArray.length;我++）{
对于（INT列：列）{//现在零列
myArray的[I] [列] = 0;
}
}
}
This is technically a code challenge. I was asked an interesting question at an interview and am hoping for some insight as the best answer I could come up with was O(2n^2) - n-squared category, but still pretty much brute force.
Let's say you have a matrix that's M by N size ( an array of arrays (int[][]) )
1 2 4 3 1
0 5 3 7 7
5 8 9 2 8
6 7 0 8 9
If a cell contains a Zero, then set that entire row and column to zero.
Making the result:
0 2 0 3 1
0 0 0 0 0
0 8 0 2 8
0 0 0 0 0
What is the fastest and/or best way to do this?
My own answer is to iterate the entire array of arrays, keep track of rows and columns to zero out, and then zero them out.
public void zeroOut(int[][] myArray){
ArrayList<Integer> rowsToZero = new....
ArrayList<Integer> columnsToZero = new....
for(int i=0; i<myArray.length; i++){ // record which rows and columns will be zeroed
for(int j=0; j<myArray[i].length; i++){
if(myArray[i][j] == 0){
if(!rowsToZero.contains(i)) rowsToZero.add(i);
if(!columnsToZero.contains(j)) columnsToZero.add(j);
}
}
}
for(int row : rows){ // now zero the rows
myArray[row] = int[myArray.length];
}
for(int i=0; i<myArray.length; i++){
for(int column: columns){ // now zero the columns
myArray[i][column] = 0;
}
}
}
Is there a better algorithm? Is there a better data-structure to represent this matrix?
Seems no one really came up with a significantly faster/better algorithm so far, so this one seems to be it. Thanks for your input everyone.
public void zeroOut(int[][] myArray){
ArrayList<Integer> rowsToZero = new....
ArrayList<Integer> columnsToZero = new....
for(int i=0; i<myArray.length; i++){ // record which rows and columns will be zeroed
for(int j=0; j<myArray[i].length; i++){
if(myArray[i][j] == 0){
if(!rowsToZero.contains(i)) rowsToZero.add(i);
if(!columnsToZero.contains(j)) columnsToZero.add(j);
}
}
}
for(int row : rows){ // now zero the rows
myArray[row] = int[myArray.length];
}
for(int i=0; i<myArray.length; i++){
for(int column: columns){ // now zero the columns
myArray[i][column] = 0;
}
}
}
这篇关于算法以修改的矩阵和设定列和行到零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
