如果该行或列包含0，则将matrix中的每个单元格设置为0

给定一个0和1的N×Nmatrix。 将包含0的所有行全部设置为0 ，并将每个包含0列全部设置为0 。

例如

 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 

一名微软工程师告诉我，有一个解决scheme不涉及额外的内存，只有两个布尔variables和一个通行证，所以我正在寻找答案。

顺便说一句，想象它是一个位matrix，因此只允许1s和0s在matrix中。

Answer 1

好吧，我已经累了，因为这是凌晨3点，但是我有第一次尝试在matrix中的每个数字正好2次通过，所以在O（NxN），它是matrix的大小是线性的。

我使用第一列和第一行作为标记来知道哪里是行/列只有1的。 那么，如果第一行/列都是1，则有2个variablesl和c要记住。 所以第一遍设置标记并将其余的重置为0。

第二遍在行和列标记为1的地方设置1，根据l和c重设第一行/列。

我强烈地怀疑，我可以在一次传球中完成，因为开始时的方格取决于最终的方格。 也许我的第二关可以变得更高效

 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) 

Answer 2

这不能一次完成，因为在任何顺序之前和之后，单个位对位有影响。 IOW无论你排列什么样的顺序，你都可能会遇到一个0，这意味着你必须返回并将前一个1更改为0。

更新

人们似乎认为通过将N限制在某个固定值（比如说8）可以解决这个问题。 那么这是a）错过了这一点，b）不是原来的问题。 我不会发表一个关于sorting的问题，并期待一个开始“假设你只想sorting8件事”的答案。

也就是说，如果你知道N实际上只限于8，那么这是一个合理的方法。我的回答上面回答了没有这种限制的原始问题。

Answer 3

所以我的想法是使用最后一行/列中的值作为标志来指示相应列/行中的所有值是否都是1。

在整个matrix中使用Zig Zag扫描 ，除了最后一行/列。 在每个元素处，您将最后一行/列中的值设置为自身与当前元素中的值的逻辑与。 换句话说，如果你点击0，最后一行/列将被设置为0.如果你是1，那么最后一行/列的值只有在已经是1时才是1。 在任何情况下，将当前元素设置为0。

完成后，如果相应的列/行填充1，则最后一行/列应该有1。

通过最后一行和一列进行线性扫描并查找1。 在最后一行和一列均为1的matrix体中的相应元素中设置1。

编码这将是棘手的，以避免错误的一个错误等，但它应该一次工作。

Answer 4

我在这里有一个解决scheme，它运行在一个单一的通行证，并做所有处理“就地”没有额外的内存（除了增长的堆栈）。

它使用recursion来延迟零的写入，这当然会破坏其他行和列的matrix：

 #include <iostream> /** * The idea with my algorithm is to delay the writing of zeros * till all rows and cols can be processed. I do this using * recursion: * 1) Enter Recursive Function: * 2) Check the row and col of this "corner" for zeros and store the results in bools * 3) Send recursive function to the next corner * 4) When the recursive function returns, use the data we stored in step 2 * to zero the the row and col conditionally * * The corners I talk about are just how I ensure I hit all the row's a cols, * I progress through the matrix from (0,0) to (1,1) to (2,2) and on to (n,n). * * For simplicities sake, I use ints instead of individual bits. But I never store * anything but 0 or 1 so it's still fair ;) */ // ================================ // Using globals just to keep function // call syntax as straight forward as possible int n = 5; int m[5][5] = { { 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 } }; // ================================ // Just declaring the function prototypes void processMatrix(); void processCorner( int cornerIndex ); bool checkRow( int rowIndex ); bool checkCol( int colIndex ); void zeroRow( int rowIndex ); void zeroCol( int colIndex ); void printMatrix(); // This function primes the pump void processMatrix() { processCorner( 0 ); } // Step 1) This is the heart of my recursive algorithm void processCorner( int cornerIndex ) { // Step 2) Do the logic processing here and store the results bool rowZero = checkRow( cornerIndex ); bool colZero = checkCol( cornerIndex ); // Step 3) Now progress through the matrix int nextCorner = cornerIndex + 1; if( nextCorner < n ) processCorner( nextCorner ); // Step 4) Finially apply the changes determined earlier if( colZero ) zeroCol( cornerIndex ); if( rowZero ) zeroRow( cornerIndex ); } // This function returns whether or not the row contains a zero bool checkRow( int rowIndex ) { bool zero = false; for( int i=0; i<n && !zero; ++i ) { if( m[ rowIndex ][ i ] == 0 ) zero = true; } return zero; } // This is just a helper function for zeroing a row void zeroRow( int rowIndex ) { for( int i=0; i<n; ++i ) { m[ rowIndex ][ i ] = 0; } } // This function returns whether or not the col contains a zero bool checkCol( int colIndex ) { bool zero = false; for( int i=0; i<n && !zero; ++i ) { if( m[ i ][ colIndex ] == 0 ) zero = true; } return zero; } // This is just a helper function for zeroing a col void zeroCol( int colIndex ) { for( int i=0; i<n; ++i ) { m[ i ][ colIndex ] = 0; } } // Just a helper function for printing our matrix to std::out void printMatrix() { std::cout << std::endl; for( int y=0; y<n; ++y ) { for( int x=0; x<n; ++x ) { std::cout << m[y][x] << " "; } std::cout << std::endl; } std::cout << std::endl; } // Execute! int main() { printMatrix(); processMatrix(); printMatrix(); } 

Answer 5

我不认为这是可行的。 当你在第一个正方形上，它的值是1时，你无法知道同一行和列中其他方块的值是多less。 所以你必须检查这些，如果有一个零，返回到第一个正方形，并将其值更改为零。 我build议在两遍中做 – 第一遍收集有关哪些行和列必须清零的信息（信息存储在一个数组中，所以我们使用一些额外的内存）。 第二遍更改值。 我知道这不是你正在寻找的解决scheme，但我认为这是一个实际的解决scheme。 您给出的限制使问题无法解决。

Answer 6

我可以用两个整数variables和两遍（最多32行和列…）

 bool matrix[5][5] = { {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} }; int CompleteRows = ~0; int CompleteCols = ~0; // Find the first 0 for (int row = 0; row < 5; ++row) { for (int col = 0; col < 5; ++col) { CompleteRows &= ~(!matrix[row][col] << row); CompleteCols &= ~(!matrix[row][col] << col); } } for (int row = 0; row < 5; ++row) for (int col = 0; col < 5; ++col) matrix[row][col] = (CompleteRows & (1 << row)) && (CompleteCols & (1 << col)); 

Answer 7

另一个需要两遍的解决scheme是在水平和垂直方向积累AND：

 1 0 1 1 0 | 0 0 1 1 1 0 | 0 1 1 1 1 1 | 1 1 0 1 1 1 | 0 1 1 1 1 1 | 1 ----------+ 0 0 1 1 0 

我以为我可以用奇偶校验位 ， 汉明码或dynamic编程devise这样的algorithm，可能使用这两个布尔值作为2位数，但是我还没有成功。

你可以请你的工程师重新检查问题陈述，让我们知道吗？ 如果确实有解决办法，我想继续解决这个问题。

Answer 8

保持一个variables来跟踪所有的行在一起。

如果一行是-1（全1），则将下一行作为该variables的引用

如果一行是什么，但它是一个0.你可以做一切通过。 伪代码：

 foreach (my $row) rows { $andproduct = $andproduct & $row; if($row != -1) { zero out the row } else { replace row with a reference to andproduct } } 

这应该是一回事，但是这里有一个假设：N足够小，CPU可以在单行上进行算术运算，否则你需要循环遍历每一行来确定它是否全部1s与否，我相信。 但是，考虑到你要求的algorithm，而不是限制我的硬件，我只是开始我的答案，“build立一个支持N位算术的CPU …”

下面是一个例子，它是如何在C中完成的。注意我认为值和arr一起表示数组，p和numproduct是我的迭代器，AND产品variables用来实现这个问题。 （我可以通过指针算术循环来validation我的工作，但一旦足够了！）

 int main() { int values[] = { -10, 14, -1, -9, -1 }; /* From the problem spec, converted to decimal for my sanity */ int *arr[5] = { values, values+1, values+2, values+3, values+4 }; int **p; int numproduct = 127; for(p = arr; p < arr+5; ++p) { numproduct = numproduct & **p; if(**p != -1) { **p = 0; } else { *p = &numproduct; } } /* Print our array, this loop is just for show */ int i; for(i = 0; i < 5; ++i) { printf("%x\n",*arr[i]); } return 0; } 

这会产生0,0,6,0,6，这是给定input的结果。

或者在PHP中，如果人们认为我在C中的游戏是作弊的（我build议你不要这样做，因为我应该能够以任何方式存储matrix）：

 <?php $values = array(-10, 14, -1, -9, -1); $numproduct = 127; for($i = 0; $i < 5; ++$i) { $numproduct = $numproduct & $values[$i]; if($values[$i] != -1) { $values[$i] = 0; } else { $values[$i] = &$numproduct; } } print_r($values); 

我错过了什么吗？

Answer 9

好的挑战。 这种解决scheme只使用在堆栈上创build的两个布尔值，但是由于函数是recursion的，所以在堆栈上多次创build布尔值。

 typedef unsigned short WORD; typedef unsigned char BOOL; #define true 1 #define false 0 BYTE buffer[5][5] = { 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 }; int scan_to_end(BOOL *h,BOOL *w,WORD N,WORD pos_N) { WORD i; for(i=0;i<N;i++) { if(!buffer[i][pos_N]) *h=false; if(!buffer[pos_N][i]) *w=false; } return 0; } int set_line(BOOL h,BOOL w,WORD N,WORD pos_N) { WORD i; if(!h) for(i=0;i<N;i++) buffer[i][pos_N] = false; if(!w) for(i=0;i<N;i++) buffer[pos_N][i] = false; return 0; } int scan(int N,int pos_N) { BOOL h = true; BOOL w = true; if(pos_N == N) return 0; // Do single scan scan_to_end(&h,&w,N,pos_N); // Scan all recursive before changeing data scan(N,pos_N+1); // Set the result of the scan set_line(h,w,N,pos_N); return 0; } int main(void) { printf("Old matrix\n"); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]); scan(5,0); printf("New matrix\n"); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[0][0],(WORD)buffer[0][1],(WORD)buffer[0][2],(WORD)buffer[0][3],(WORD)buffer[0][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[1][0],(WORD)buffer[1][1],(WORD)buffer[1][2],(WORD)buffer[1][3],(WORD)buffer[1][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[2][0],(WORD)buffer[2][1],(WORD)buffer[2][2],(WORD)buffer[2][3],(WORD)buffer[2][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[3][0],(WORD)buffer[3][1],(WORD)buffer[3][2],(WORD)buffer[3][3],(WORD)buffer[3][4]); printf( "%d,%d,%d,%d,%d \n", (WORD)buffer[4][0],(WORD)buffer[4][1],(WORD)buffer[4][2],(WORD)buffer[4][3],(WORD)buffer[4][4]); system( "pause" ); return 0; } 

这样扫描的模式如下：

 s,s,s,s,s s,0,0,0,0 s,0,0,0,0 s,0,0,0,0 s,0,0,0,0 

 0,s,0,0,0 s,s,s,s,s 0,s,0,0,0 0,s,0,0,0 0,s,0,0,0 

等等

然后在每个扫描函数的返回值上更改此模式中的值。 （自下而上）：

 0,0,0,0,c 0,0,0,0,c 0,0,0,0,c 0,0,0,0,c c,c,c,c,c 

 0,0,0,c,0 0,0,0,c,0 0,0,0,c,0 c,c,c,c,c 0,0,0,c,0 

等等

Answer 10

好的，这是一个解决scheme

• 只使用一个超长的价值工作存储。
• 不使用recursion。
• 一次只有N次，甚至N * N次。
• 将为N的其他值工作，但将需要新的#defines。

 #include <stdio.h> #define BIT30 (1<<24) #define COLMASK 0x108421L #define ROWMASK 0x1fL 

 unsigned long long STARTGRID = ((0x10 | 0x0 | 0x4 | 0x2 | 0x0) << 20) | ((0x00 | 0x8 | 0x4 | 0x2 | 0x0) << 15) | ((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 10) | ((0x10 | 0x0 | 0x4 | 0x2 | 0x1) << 5) | ((0x10 | 0x8 | 0x4 | 0x2 | 0x1) << 0); void dumpGrid (char* comment, unsigned long long theGrid) { char buffer[1000]; buffer[0]='\0'; printf ("\n\n%s\n",comment); for (int j=1;j<31; j++) { if (j%5!=1) printf( "%s%s", ((theGrid & BIT30)==BIT30)? "1" : "0",(((j%5)==0)?"\n" : ",") ); theGrid = theGrid << 1; } } int main (int argc, const char * argv[]) { unsigned long long rowgrid = STARTGRID; unsigned long long colGrid = rowgrid; unsigned long long rowmask = ROWMASK; unsigned long long colmask = COLMASK; dumpGrid("Initial Grid", rowgrid); for (int i=0; i<5; i++) { if ((rowgrid & rowmask)== rowmask) rowgrid |= rowmask; else rowgrid &= ~rowmask; if ((colGrid & colmask) == colmask) colmask |= colmask; else colGrid &= ~colmask; rowmask <<= 5; colmask <<= 1; } colGrid &= rowgrid; dumpGrid("RESULT Grid", colGrid); return 0; } 

Answer 11

其实。 如果您只是想运行algorithm并打印出结果（即不能恢复它们，那么可以轻松地一次完成）。当您在运行algorithm时尝试修改数组时，会遇到麻烦。

这里是我的解决scheme它只涉及ANDING行（列，列）值给一个givein（i，j）的元素并打印出来。

 #include <iostream> #include "stdlib.h" void process(); int dim = 5; bool m[5][5]{{1,0,1,1,1},{0,1,1,0,1},{1,1,1,1,1},{1,1,1,1,1},{0,0,1,1,1}}; int main() { process(); return 0; } void process() { for(int j = 0; j < dim; j++) { for(int i = 0; i < dim; i++) { std::cout << ( (m[0][j] & m[1][j] & m[2][j] & m[3][j] & m[4][j]) & (m[i][0] & m[i][1] & m[i][2] & m[i][3] & m[i][4]) ); } std::cout << std::endl; } } 

Answer 12

问题可以一次性解决

将matrix保存在一个i X j数组中。

 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 one each pass save the values of i and j for an element which is 0 in arrays a and b when first row is scanned a= 1 b = 2,5 when second row is scanned a=1,2 b= 1,2,5 when third row is scanned no change when fourth row is scanned a= 1,2,4 and b= 1,2,5 when fifth row is scanned no change . 

现在把所有值都打印为0，保存在a和b中的i和j的值是1，即（3,3）（3,4）（5,3）和（5,4）

Answer 13

我试图用C＃解决这个问题。

我用了两个循环variables（i和j），除了实际的matrix，n代表了它的维数

我试过的逻辑是：

1. 计算matrix中每个同心矩形所涉及的行和列的“与”
2. 将它存储在angular落单元格中（我将它们按逆时针顺序存储）
3. 当评估一个特定的方块时，使用两个boolvariables来保留两个angular的值。
4. 当外环（i）在中途时，该过程将结束。
5. 根据angular细胞评估其他细胞的结果（对于我的其余部分）。 在此过程中跳过angular落单元格。
6. 当我到达n时，除了angular单元之外，所有的单元都会有其结果。
7. 更新angular落单元格。 除了在问题中提到的单通道约束之外，这是一个额外的长度为n / 2的迭代。

码：

 void Evaluate(bool [,] matrix, int n) { bool tempvar1, tempvar2; for (var i = 0; i < n; i++) { tempvar1 = matrix[i, i]; tempvar2 = matrix[n - i - 1, n - i - 1]; var j = 0; for (j = 0; j < n; j++) { if ((i < n/2) || (((n % 2) == 1) && (i == n/2) && (j <= i))) { // store the row and col & results in corner cells of concentric squares tempvar1 &= matrix[j, i]; matrix[i, i] &= matrix[i, j]; tempvar2 &= matrix[n - j - 1, n - i - 1]; matrix[n - i - 1, n - i - 1] &= matrix[n - i - 1, n - j - 1]; } else { // skip corner cells of concentric squares if ((j == i) || (j == n - i - 1)) continue; // calculate the & values for rest of them matrix[i, j] = matrix[i, i] & matrix[n - j - 1, j]; matrix[n - i - 1, j] = matrix[n - i - 1, n - i - 1] & matrix[n - j - 1, j]; if ((i == n/2) && ((n % 2) == 1)) { // if n is odd matrix[i, n - j - 1] = matrix[i, i] & matrix[j, n - j - 1]; } } } if ((i < n/2) || (((n % 2) == 1) && (i <= n/2))) { // transfer the values from temp variables to appropriate corner cells of its corresponding square matrix[n - i - 1, i] = tempvar1; matrix[i, n - i - 1] = tempvar2; } else if (i == n - 1) { // update the values of corner cells of each concentric square for (j = n/2; j < n; j++) { tempvar1 = matrix[j, j]; tempvar2 = matrix[n - j - 1, n - j - 1]; matrix[j, j] &= matrix[n - j - 1, j]; matrix[n - j - 1, j] &= tempvar2; matrix[n - j - 1, n - j - 1] &= matrix[j, n - j - 1]; matrix[j, n - j - 1] &= tempvar1; } } } } 

Answer 14

虽然不可能在给定约束的情况下进行，但最节约空间的方法是通过以重叠的交替的行/列方式遍历matrix，这将形成类似于以锯齿形方式布置砖的图案：

 ----- |---- ||--- 

Answer 15

—

Answer 16

|-

使用这个，你可以按照指示在每一行/列中进行操作，如果你在任何时候遇到一个0，就设置一个布尔variables，然后重新遍历该行/列，随着时间的推移将条目设置为0。

这将不需要额外的内存，只会使用一个布尔variables。 不幸的是，如果“远”边被设置为全部为0，那么这是最坏的情况，并且你将整个arrays遍历两次。

Answer 17

创build一个结果matrix并将所有值设置为1.遇到0时，立即遍历数据matrix，将结果matrix行列设置为0

在第一遍结束时，结果matrix将有正确的答案。

看起来很简单。 有没有我失踪的诡计？ 你不允许使用结果集吗？

编辑：

看起来像一个F＃函数，但这是有点作弊，因为即使你正在做一个单一的传递，函数可以是recursion的。

面试官似乎在试图弄清楚你是否知道函数式编程。

Answer 18

那么，我想出了一个使用4个bool和2个循环计数器的单步就地（非recursion）解决scheme。 我没有设法减less到2布尔和2整数，但我不会感到惊讶，如果这是可能的。 它会对每个单元执行大约3次读取和3次写入操作，它应该是O（N ^ 2），即。 线性的数组大小。

花了我几个小时来解答这个问题 – 我不想在面试的压力下拿出来！ 如果我做了一个booboo，我太累了，不能发现它…

嗯…我select将“单程”定义为在matrix中进行一次扫描，而不是触摸每个值一次！ 🙂

 #include <stdio.h> #include <memory.h> #define SIZE 5 typedef unsigned char u8; u8 g_Array[ SIZE ][ SIZE ]; void Dump() { for ( int nRow = 0; nRow < SIZE; ++nRow ) { for ( int nColumn = 0; nColumn < SIZE; ++nColumn ) { printf( "%d ", g_Array[ nRow ][ nColumn ] ); } printf( "\n" ); } } void Process() { u8 fCarriedAlpha = true; u8 fCarriedBeta = true; for ( int nStep = 0; nStep < SIZE; ++nStep ) { u8 fAlpha = (nStep > 0) ? g_Array[ nStep-1 ][ nStep ] : true; u8 fBeta = (nStep > 0) ? g_Array[ nStep ][ nStep - 1 ] : true; fAlpha &= g_Array[ nStep ][ nStep ]; fBeta &= g_Array[ nStep ][ nStep ]; g_Array[ nStep-1 ][ nStep ] = fCarriedBeta; g_Array[ nStep ][ nStep-1 ] = fCarriedAlpha; for ( int nScan = nStep + 1; nScan < SIZE; ++nScan ) { fBeta &= g_Array[ nStep ][ nScan ]; if ( nStep > 0 ) { g_Array[ nStep ][ nScan ] &= g_Array[ nStep-1 ][ nScan ]; g_Array[ nStep-1][ nScan ] = fCarriedBeta; } fAlpha &= g_Array[ nScan ][ nStep ]; if ( nStep > 0 ) { g_Array[ nScan ][ nStep ] &= g_Array[ nScan ][ nStep-1 ]; g_Array[ nScan ][ nStep-1] = fCarriedAlpha; } } g_Array[ nStep ][ nStep ] = fAlpha & fBeta; for ( int nScan = nStep - 1; nScan >= 0; --nScan ) { g_Array[ nScan ][ nStep ] &= fAlpha; g_Array[ nStep ][ nScan ] &= fBeta; } fCarriedAlpha = fAlpha; fCarriedBeta = fBeta; } } int main() { memset( g_Array, 1, sizeof(g_Array) ); g_Array[0][1] = 0; g_Array[0][4] = 0; g_Array[1][0] = 0; g_Array[1][4] = 0; g_Array[3][1] = 0; printf( "Input:\n" ); Dump(); Process(); printf( "\nOutput:\n" ); Dump(); return 0; } 

Answer 19

i hope you enjoy my 1-pass c# solution

you can retrieve an element with O(1) and only need the space of one row and one column of the matrix

 bool[][] matrix = { new[] { true, false, true, true, false }, // 10110 new[] { false, true, true, true, false }, // 01110 new[] { true, true, true, true, true }, // 11111 new[] { true, false, true, true, true }, // 10111 new[] { true, true, true, true, true } // 11111 }; int n = matrix.Length; bool[] enabledRows = new bool[n]; bool[] enabledColumns = new bool[n]; for (int i = 0; i < n; i++) { enabledRows[i] = true; enabledColumns[i] = true; } for (int rowIndex = 0; rowIndex < n; rowIndex++) { for (int columnIndex = 0; columnIndex < n; columnIndex++) { bool element = matrix[rowIndex][columnIndex]; enabledRows[rowIndex] &= element; enabledColumns[columnIndex] &= element; } } for (int rowIndex = 0; rowIndex < n; rowIndex++) { for (int columnIndex = 0; columnIndex < n; columnIndex++) { bool element = enabledRows[rowIndex] & enabledColumns[columnIndex]; Console.Write(Convert.ToInt32(element)); } Console.WriteLine(); } /* 00000 00000 00110 00000 00110 */ 

Answer 20

1 pass, 2 booleans. I just have to assume the integer indexes in the iterations don't count.

This is not a complete solution but I can't get pass this point.

If I could only determine if a 0 is an original 0 or a 1 that was converted to a 0 then I wouldn't have to use -1's and this would work.

My output is like this:

 -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 

The originality of my approach is using the first half of the examination of a row or column to determine if it contains a 0 and the last half to set the values – this is done by looking at x and width-x and then y and height-y in each iteration. Based on the results of the first half of the iteration, if a 0 in the row or column was found, I use the last half of the iteration to change the 1's to -1's.

I just realized this could be done with only 1 boolean leaving 1 to …?

I'm posting this hoping someone might say, "Ah, just do this…" (And I spent way too much time on it not to post.)

Here's the code in VB:

 Dim D(,) As Integer = {{1, 0, 1, 1, 1}, {0, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}, {0, 0, 1, 1, 1}} Dim B1, B2 As Boolean For y As Integer = 0 To UBound(D) B1 = True : B2 = True For x As Integer = 0 To UBound(D) // Scan row for 0's at x and width - x positions. Halfway through I'll konw if there's a 0 in this row. //If a 0 is found set my first boolean to false. If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then If D(x, y) = 0 Or D(UBound(D) - x, y) = 0 Then B1 = False End If //If the boolean is false then a 0 in this row was found. Spend the last half of this loop //updating the values. This is where I'm stuck. If I change a 1 to a 0 it will cause the column //scan to fail. So for now I change to a -1. If there was a way to change to 0 yet later tell if //the value had changed this would work. If Not B1 Then If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then If D(x, y) = 1 Then D(x, y) = -1 If D(UBound(D) - x, y) = 1 Then D(UBound(D) - x, y) = -1 End If End If //These 2 block do the same as the first 2 blocks but I switch x and y to do the column. If x <= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then If D(y, x) = 0 Or D(y, UBound(D) - x) = 0 Then B2 = False End If If Not B2 Then If x >= (Math.Ceiling((UBound(D) + 1) / 2) - 1) Then If D(y, x) = 1 Then D(y, x) = -1 If D(y, UBound(D) - x) = 1 Then D(y, UBound(D) - x) = -1 End If End If Next Next 

Answer 21

No one is using binary forms? since it's only 1 and 0. We can use binary vectors.

 def set1(M, N): '''Set 1/0s on M according to the rules. M is a list of N integers. Each integer represents a binary array, eg, 000100''' ruler = 2**N-1 for i,v in enumerate(M): ruler = ruler & M[i] M[i] = M[i] if M[i]==2**N-1 else 0 # set i-th row to all-0 if not all-1s for i,v in enumerate(M): if M[i]: M[i] = ruler return M 

Here's the test:

 M = [ 0b10110, 0b01110, 0b11111, 0b10111, 0b11111 ] print "Before..." for i in M: print "{:0=5b}".format(i) M = set1(M, len(M)) print "After..." for i in M: print "{:0=5b}".format(i) 

而输出：

 Before... 10110 01110 11111 10111 11111 After... 00000 00000 00110 00000 00110 

Answer 22

You can do something like this to use one pass but an input and output matrix:

 output(x,y) = col(xy) & row(xy) == 2^n 

where col(xy) is the bits in the column containing the point xy ; row(xy) is the bits in the row containing the point xy . n is the size of the matrix.

Then just loop over the input. Possibly expandable to be more space efficient?

Answer 23

One matrix scan, two booleans, no recursion.

How to avoid the second pass? The second pass is needed to clear the rows or columns when the zero appeares at their end.

However this problem can be solved, because when we scan row #i we already know the row status for the row #i-1. So, while we are scanning the row #i we can simultaneously clear the row #i-1 if it is needed.

The same solution works for columns, but we need to scan rows and columns simultaneously while the data is not changed by the next iteration.

Two booleans are required to store the status of first row and first column, because their values will be changed during the execution of main part of the algorithm.

To avoid adding more booleans we are storing the "clear" flag for the rows and columns in the first row and column of the matrix.

 public void Run() { const int N = 5; int[,] m = new int[N, N] {{ 1, 0, 1, 1, 0 }, { 1, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1 }, { 1, 1, 1, 1, 1 }}; bool keepFirstRow = (m[0, 0] == 1); bool keepFirstColumn = keepFirstRow; for (int i = 1; i < N; i++) { keepFirstRow = keepFirstRow && (m[0, i] == 1); keepFirstColumn = keepFirstColumn && (m[i, 0] == 1); } Print(m); // show initial setup m[0, 0] = 1; // to protect first row from clearing by "second pass" // "second pass" is performed over i-1 row/column, // so we use one more index just to complete "second pass" over the // last row/column for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { // "first pass" - searcing for zeroes in row/column #i // when i = N || j == N it is additional pass for clearing // the previous row/column // j >= i because cells with j < i may be already modified // by "second pass" part if (i < N && j < N && j >= i) { m[i, 0] &= m[i, j]; m[0, j] &= m[i, j]; m[0, i] &= m[j, i]; m[j, 0] &= m[j, i]; } // "second pass" - clearing the row/column scanned // in the previous iteration if (m[i - 1, 0] == 0 && j < N) { m[i - 1, j] = 0; } if (m[0, i - 1] == 0 && j < N) { m[j, i - 1] = 0; } } Print(m); } // Clear first row/column if needed if (!keepFirstRow || !keepFirstColumn) { for (int i = 0; i < N; i++) { if (!keepFirstRow) { m[0, i] = 0; } if (!keepFirstColumn) { m[i, 0] = 0; } } } Print(m); Console.ReadLine(); } private static void Print(int[,] m) { for (int i = 0; i < m.GetLength(0); i++) { for (int j = 0; j < m.GetLength(1); j++) { Console.Write(" " + m[i, j]); } Console.WriteLine(); } Console.WriteLine(); } 

Answer 24

seems like the following works with no additional space requirements:

first note that multiplying the elements of the row times the elements of the line in which an element is, gives the desired value.

In order not to use any additional space (not making a new matrix and filling it up but instead apply changes to the matrix directly), start top left of the matrix and do the computation for any ixi matrix (that "starts" at (0,0)) before considering any element with any index > i.

hope this works (havent testet)

Answer 25

This is TESTED for different N in C++, and is:
ONE PASS , TWO BOOLS , NO RECURSION , NO EXTRA MEMORY , HOLDS FOR ARBITRARLY LARGE N
(So far none of the solutions here do ALL of these.)

More specifically, I'm amusing two loop counters are okay. I have two const unsigneds, which only exist rather than being computed every time for readability. The outer loop's interval is [0, N], and the inner loop's interval is [1, n – 1]. The switch statement is in the loop mostly exists to show very clearly that it really is just one pass.

Algorithm Strategy:

The first trick is to us a row and a column from the matrix itself to accumulate the content of the matrix, this memory becomes available by offloading all we really need to know from the first row and column into two booleans. The second trick is to get two passes out of one, by using the symmetry of the sub-matrix and its indices.

Algorithm Synopsis:

• Scan the first row and store if they are all ones in a boolean, do the same for the first column storing the result in a second boolean.
• For the sub-matrix excluding the first row and the first column: iterate through, left to right, top to bottom, as one would read a paragraph. Upon visiting each element, also visit the corresponding element that would be visited if visiting the sub-matrix in reverse. For each element visited AND its value into the where its row crosses the first column, and also AND its value into where its column crosses the first row.
• Once the center of the sub-matrix is reached, continue to visit the two elements simultaneously as above. However now set the visited elements' value to the AND of where its row crosses the first column, and of where its column crosses the first row. After this, the sub-matrix is complete.
• Use the two boolean variables computed at the begging to set the first row, and the first column to their correct values.

Templatized C++ Implementation:

 template<unsigned n> void SidewaysAndRowColumn(int((&m)[n])[n]) { bool fcol = m[0][0] ? true : false; bool frow = m[0][0] ? true : false; for (unsigned d = 0; d <= n; ++d) { for (unsigned i = 1; i < n; ++i) { switch (d) { case 0: frow = frow && m[d][i]; fcol = fcol && m[i][d]; break; default: { unsigned const rd = n - d; unsigned const ri = n - i; if (d * n + i < rd * n + ri) { m[ d][ 0] &= m[ d][ i]; m[ 0][ d] &= m[ i][ d]; m[ 0][ i] &= m[ d][ i]; m[ i][ 0] &= m[ i][ d]; m[rd][ 0] &= m[rd][ri]; m[ 0][rd] &= m[ri][rd]; m[ 0][ri] &= m[rd][ri]; m[ri][ 0] &= m[ri][rd]; } else { m[ d][ i] = m[ d][0] & m[0][ i]; m[rd][ri] = m[rd][0] & m[0][ri]; } break; } case n: if (!frow) m[0][i] = 0; if (!fcol) m[i][0] = 0; }; } } m[0][0] = (frow && fcol) ? 1 : 0; } 

Answer 26

Ok, I realize that it isn't quite a match, but I got it in one pass using a bool and a byte instead of two bools… close. I also wouldn't vouch for the efficiency of it but these types of questions often require less than optimal solutions.

 private static void doIt(byte[,] matrix) { byte zeroCols = 0; bool zeroRow = false; for (int row = 0; row <= matrix.GetUpperBound(0); row++) { zeroRow = false; for (int col = 0; col <= matrix.GetUpperBound(1); col++) { if (matrix[row, col] == 0) { zeroRow = true; zeroCols |= (byte)(Math.Pow(2, col)); // reset this column in previous rows for (int innerRow = 0; innerRow < row; innerRow++) { matrix[innerRow, col] = 0; } // reset the previous columns in this row for (int innerCol = 0; innerCol < col; innerCol++) { matrix[row, innerCol] = 0; } } else if ((int)(zeroCols & ((byte)Math.Pow(2, col))) > 0) { matrix[row, col] = 0; } // Force the row to zero if (zeroRow) { matrix[row, col] = 0; } } } } 

Answer 27

You can sorta do it in one pass — if you don't count accessing the matrix in random-access order, which eliminates the benefits of doing it single-pass in the first place (cache-coherence/memory-bandwidth).

[edit: simple, but wrong solution deleted]

You should get better performance than any single-pass method by doing it in two passes: one to accumulate row/column info, and one to apply it. The array (in row-major order) is accessed coherently; for arrays exceeding the cache size (but whose rows can fit in cache), data should be read from memory twice, and stored once:

 void fixmatrix2(int M[][], int rows, int cols) { bool clearZeroRow= false; bool clearZeroCol= false; for(int j=0; j < cols; ++j) { if( ! M[0][j] ) { clearZeroRow= true; } } for(int i=1; i < rows; ++i) { // scan/accumulate pass if( ! M[i][0] ) { clearZeroCol= true; } for(int j=1; j < cols; ++j) { if( ! M[i][j] ) { M[0][j]= 0; M[i][0]= 0; } } } for(int i=1; i < rows; ++i) { // update pass if( M[i][0] ) { for(int j=0; j < cols; ++j) { if( ! M[j][0] ) { M[i][j]= 0; } } } else { for(int j=0; j < cols; ++j) { M[i][j]= 0; } } if(clearZeroCol) { M[i][0]= 0; } } if(clearZeroRow) { for(int j=0; j < cols; ++j) { M[0][j]= 0; } } } 

Answer 28

The simplest solution I can think of is pasted below. The logic is to record which row and column to set zero while iterating.

 import java.util.HashSet; import java.util.Set; public class MatrixExamples { public static void zeroOut(int[][] myArray) { Set<Integer> rowsToZero = new HashSet<>(); Set<Integer> columnsToZero = new HashSet<>(); for (int i = 0; i < myArray.length; i++) { for (int j = 0; j < myArray.length; j++) { if (myArray[i][j] == 0) { rowsToZero.add(i); columnsToZero.add(j); } } } for (int i : rowsToZero) { for (int j = 0; j < myArray.length; j++) { myArray[i][j] = 0; } } for (int i : columnsToZero) { for (int j = 0; j < myArray.length; j++) { myArray[j][i] = 0; } } for (int i = 0; i < myArray.length; i++) { // record which rows and // columns will be zeroed for (int j = 0; j < myArray.length; j++) { System.out.print(myArray[i][j] + ","); if(j == myArray.length-1) System.out.println(); } } } public static void main(String[] args) { int[][] a = { { 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 } }; zeroOut(a); } } 

Answer 29

Here is my Ruby implementation with the the test included, This would take O(MN) space. If we want a real time update (like to show the results when we find zeros rather than waiting the first loop of finding zeros) we can just create another class variable like @output and whenever we find a zero we update @output and not @input .

 require "spec_helper" class Matrix def initialize(input) @input = input @zeros = [] end def solve @input.each_with_index do |row, i| row.each_with_index do |element, j| @zeros << [i,j] if element == 0 end end @zeros.each do |x,y| set_h_zero(x) set_v_zero(y) end @input end private def set_h_zero(row) @input[row].map!{0} end def set_v_zero(col) @input.size.times do |r| @input[r][col] = 0 end end end describe "Matrix" do it "Should set the row and column of Zero to Zeros" do input = [[1, 3, 4, 9, 0], [0, 3, 5, 0, 8], [1, 9, 6, 1, 9], [8, 3, 2, 0, 3]] expected = [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 9, 6, 0, 0], [0, 0, 0, 0, 0]] matrix = Matrix.new(input) expect(matrix.solve).to eq(expected) end end 

Answer 30

The code below creates a matrix of size m,n. First decide the dimensions of the matrix. I wanted to fill the matrix[m][n] with randomly with numbers between 0..10. Then create another matrix of the same dimensions and fill it with -1s (final matrix). Then iterate through the initial matrix to see if you will hit 0. When you hit on location(x,y), go to the final matrix and fill the row x with 0s and column y with 0s. At the end read through the final matrix, if the value is -1 (original value) copy the value in the same location of the initial matrix to final.

 public static void main(String[] args) { int m = 5; int n = 4; int[][] matrixInitial = initMatrix(m, n); // 5x4 matrix init randomly int[][] matrixFinal = matrixNull(matrixInitial, m, n); for (int i = 0; i < m; i++) { System.out.println(Arrays.toString(matrixFinal[i])); } } public static int[][] matrixNull(int[][] matrixInitial, int m, int n) { int[][] matrixFinal = initFinal(m, n); // create a matrix with mxn and init it with all -1 for (int i = 0; i < m; i++) { // iterate in initial matrix for (int j = 0; j < n; j++) { if(matrixInitial[i][j] == 0){ // if a value is 0 make rows and columns 0 makeZeroX(matrixFinal, i, j, m, n); } } } for (int i = 0; i < m; i++) { // if value is -1 (original) copy from initial for (int j = 0; j < n; j++) { if(matrixFinal[i][j] == -1) { matrixFinal[i][j] = matrixInitial[i][j]; } } } return matrixFinal; } private static void makeZeroX(int[][] matrixFinal, int x, int y, int m, int n) { for (int j = 0; j < n; j++) { // make all row 0 matrixFinal[x][j] = 0; } for(int i = 0; i < m; i++) { // make all column 0 matrixFinal[i][y] = 0; } } private static int[][] initMatrix(int m, int n) { int[][] matrix = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { Random rn = new Random(); int random = rn.nextInt(10); matrix[i][j] = random; } } for (int i = 0; i < m; i++) { System.out.println(Arrays.toString(matrix[i])); } System.out.println("******"); return matrix; } private static int[][] initFinal(int m, int n) { int[][] matrix = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = -1; } } return matrix; } // another approach /** * @param matrixInitial * @param m * @param n * @return */ private static int[][] matrixNullNew(int[][] matrixInitial, int m, int n) { List<Integer> zeroRowList = new ArrayList<>(); // Store rows with 0 List<Integer> zeroColumnList = new ArrayList<>(); // Store columns with 0 for (int i = 0; i < m; i++) { // read through the matrix when you hit 0 add the column to zeroColumnList and add // the row to zeroRowList for (int j = 0; j < n; j++) { if (matrixInitial[i][j] == 0) { if (!zeroRowList.contains(i)) { zeroRowList.add(i); } if (!zeroColumnList.contains(j)) { zeroColumnList.add(j); } } } } for (int a = 0; a < m; a++) { if (zeroRowList.contains(a)) { // if the row has 0 for (int b = 0; b < n; b++) { matrixInitial[a][b] = 0; // replace all row with zero } } } for (int b = 0; b < n; b++) { if (zeroColumnList.contains(b)) { // if the column has 0 for (int a = 0; a < m; a++) { matrixInitial[a][b] = 0; // replace all column with zero } } } return matrixInitial; } 

Answer 31

这是我的解决scheme。 As you can see from the code, given a M * N matrix, it sets the entire row to zero once it inspects a zero in that row.the time complexity of my solution is O(M * N) . I am sharing the whole class which has a static populated array for testing and a display array method to see the result in the console.

 public class EntireRowSetToZero { static int arr[][] = new int[3][4]; static { arr[0][0] = 1; arr[0][1] = 9; arr[0][2] = 2; arr[0][3] = 2; arr[1][0] = 1; arr[1][1] = 5; arr[1][2] = 88; arr[1][3] = 7; arr[2][0] = 0; arr[2][1] = 8; arr[2][2] = 4; arr[2][3] = 4; } public static void main(String[] args) { displayArr(EntireRowSetToZero.arr, 3, 4); setRowToZero(EntireRowSetToZero.arr); System.out.println("--------------"); displayArr(EntireRowSetToZero.arr, 3, 4); } static int[][] setRowToZero(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { if(arr[i][j]==0){ arr[i]=new int[arr[i].length]; } } } return arr; } static void displayArr(int[][] arr, int n, int k) { for (int i = 0; i < n; i++) { for (int j = 0; j < k; j++) { System.out.print(arr[i][j] + " "); } System.out.println(""); } } 

}