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

保持一个单独的变量来跟踪所有 AND 行是什么。

如果一行为 -1(全部为1) ，则将下一行作为对该变量的引用

如果一行是任何东西，但是，它是一个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 做算术在一个单一的行，否则你将需要循环遍历每一行，以确定是否所有的1，我相信。但是考虑到你问的是算法，而不是限制我的硬件，我会以“构建一个支持 N 位算法的 CPU...”开始我的回答

下面是一个如何在 C 中实现的例子。注意，我认为值和 arr 一起表示数组，p 和 numproduct 是迭代器，AND 产品变量用来实现这个问题。(我本可以用指针算法循环遍历 arr 来验证我的工作，但一次就够了!)

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，这是给定输入的结果。

或者在 PHP 中，如果人们认为我在 C 中的堆栈游戏是作弊的(我建议你这不是作弊，因为我应该能够以任何我喜欢的方式存储矩阵) :

<?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);

我错过了什么吗？

我这里有一个解决方案，它在一个单独的传递中运行，并且在没有额外内存的情况下“就地”进行所有处理(除了增加堆栈)。

它使用递归来延迟零的写入，这当然会破坏其他行和协议的矩阵:

#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();
}

嗯，我想出了一个单通道，就地(非递归)解决方案，使用4个布尔和2个循环计数器。我还没有设法把它减少到2 bools 和2 int，但是如果可能的话，我不会感到惊讶。它对每个单元格执行3次读写操作，应该是 O (N ^ 2)。数组大小呈线性。

我花了好几个小时才想出这个问题——我可不想在面试的压力下想出这个问题！如果我犯了错，我会累得发现不了。

嗯... ... 我选择将“单次传递”定义为扫描矩阵，而不是触摸每个值一次! : -)

#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;
}

你可以一次性完成——如果你不把随机访问次序计算在内的话，这就消除了一次性完成的好处(缓存一致性/内存带宽)。

[编辑: 简单，但错误的解决方案删除]

通过两次传递，您应该比任何单次传递方法获得更好的性能: 一次是累积行/列信息，另一次是应用它。数组(以行为主顺序)是连贯访问的; 对于超过缓存大小(但其行可以放入缓存)的数组，数据应该从内存读取两次，并存储一次:

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;
}
}
}

好的，这是一个 的解决方案

• 只使用一个额外的长值作为工作存储。
• 不使用递归。
• 一次只有 N，甚至 N * N 都没有。
• 将工作的其他值 N，但将需要新的 # 定义。

#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;
}

希望你喜欢我的一次性 C # 解决方案

你可以用 O (1)检索一个元素，只需要 矩阵的一行一列的空间

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
*/

好吧，我知道这不是很匹配，但是我用一个 bool 和一个字节，而不是两个 bool 一次就搞定了，很接近了。我也不敢保证它的效率，但这类问题往往需要的不是最佳解决方案。

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; }
}
}
}

1次传递，2个布尔值。我只需要假设迭代中的整数索引不计数。

这不是一个完整的解决方案，但我不能通过这一点。

如果我只能确定0是原始的0还是转换成0的1那么我就不用用 -1了，这样就可以了。

我的输出是这样的:

-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，而后半部分来设置值——这是通过在每次迭代中查看 x 和 width-x，然后查看 y 和 height-y 来完成的。基于迭代的前半部分的结果，如果在行或列中找到0，我将使用迭代的后半部分将1更改为 -1。

我刚刚意识到只需要一个布尔值就可以做到这一点？

我发布这篇文章是希望有人会说，“啊，就这么做吧... ...”(我花了太多时间在上面，不能不发。)

下面是 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

你可以这样做，使用一个传递，但一个输入和输出矩阵:

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

其中 col(xy)是包含点 xy的列中的位; row(xy)是包含点 xy的行中的位。n是矩阵的大小。

然后只是循环输入。可能扩展更有效的空间？

没有人使用二进制形式? 因为它只是1和0。我们可以使用二进制向量。

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, e.g.,
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

测试是这样的:

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

事实上。如果您只是想运行算法并打印出结果(即不恢复它们，那么这可以很容易地一次完成。当您在运行算法时试图修改数组时，麻烦就来了。

这里是我的解决方案，它只是涉及到 ANDing 的行/列值的给定(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;
}
}

这个问题可以一次解决

将矩阵保存在 iXj 数组中。

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 .

现在将保存在 a 和 b 中的 i 和 j 的值全部打印为0 其余的值是1 ie (3,3)(3,4)(5,3)和(5,4)

一次矩阵扫描，两次布尔值，没有递归。

如何避免第二次通过？ 当零出现在行或列的末尾时，需要第二次传递来清除这些行或列。

然而，这个问题可以解决，因为当我们扫描行 # i 时，我们已经知道行 # i-1的行状态。因此，当我们扫描行 # i 时，如果需要，我们可以同时清除行 # i-1。

同样的解决方案也适用于列，但是我们需要同时扫描行和列，而下一次迭代不会更改数据。

存储第一行和第一列的状态需要两个布尔值，因为它们的值将在算法的主要部分执行期间更改。

为了避免添加更多的布尔值，我们为矩阵的第一行和第一列中的行和列存储了“ clear”标志。

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();
}

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

我使用了两个循环变量(i 和 j) ，除了实际的矩阵和 n 表示它的维数

我尝试的逻辑是:

1. 计算矩阵的每个同心平方中涉及的行和二进制数的 AND
2. 将其存储在角落的单元格中(我将它们按逆时针顺序存储)
3. 两个布尔变量用于保留两个角的值时，评估一个特定的平方。
4. 当外部循环(i)处于中途时，这个过程将结束。
5. 基于角点单元评估其他单元的结果(对于其余的 i)。在此过程中跳过角单元格。
6. 当我到达 n 时，除了角点单元格，所有单元格都有结果。
7. 更新角牢房。这是对 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;
}
}
}
}

下列作品似乎没有额外的空间要求:

首先要注意的是，将行的元素乘以元素所在的行的元素，就得到了所需的值。

为了避免使用任何额外的空间(不创建一个新的矩阵并填充它，而是直接对矩阵进行修改) ，在考虑任何索引 > i 的元素之前，从矩阵的左上角开始计算任何 ixi 矩阵(从(0,0)开始计算)。

希望这个有用(不测试)

这是 C + + 中不同 N 的 测试过，是:
对于任意大 N，ONE PASS ，两声，没有递归，没有额外记忆，< strong > HOLDS
(到目前为止，这里没有一个解决方案可以做到所有这些。)

更确切地说，我觉得两个循环计数器是可以的。我有两个常量无符号，它们只存在而不是每次都被计算以便可读。外循环的间隔为[0，N ] ，内循环的间隔为[1，n-1]。Switch 语句主要存在于循环中，以非常清楚地表明它实际上只是一次通过。

算法策略:

第一个技巧是我们从矩阵本身获得一行一列来积累矩阵的内容，这个内存可以通过将我们需要知道的第一行和第一列的所有内容分解成两个布尔值来获得。第二个技巧是利用子矩阵及其指数的对称性，从一个子矩阵中得到两次传递。

算法简介:

• 扫描第一行并存储(如果它们都是布尔值中的行) ，对第一列执行同样的操作，将结果存储在第二个布尔值中。
• 对于不包括第一行和第一列的子矩阵: 迭代，从左到右，从上到下，就像读段落一样。在访问每个元素时，还要访问相应的元素，如果反过来访问子矩阵，就会访问这些元素。对于访问过的每个元素，它的值与它的行与第一行交叉的位置相对应，它的值与它的列与第一行交叉的位置相对应。
• 一旦到达子矩阵的中心，继续像上面那样同时访问这两个元素。然而，现在将访问元素的值设置为它的行与第一行交叉的 AND，以及它的列与第一行交叉的 AND。这之后，子矩阵就完成了。
• 使用在请求时计算的两个布尔变量设置第一行，并将第一列设置为它们的正确值。

模板化 C + + 实现:

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;
}

下面是我的 Ruby 实现，其中包含了测试，这将占用 O (MN)空间。如果我们想要一个实时更新(比如当我们找到零的时候显示结果，而不是等待第一个循环找到零) ，我们可以创建另一个类变量，比如 @output，当我们找到一个零的时候，我们更新 @output而不是 @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

我能想到的最简单的解决方案粘贴在下面。其逻辑是记录迭代时将哪一行和哪一列设置为零。

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);
}
}

下面的代码创建一个大小为 m，n 的矩阵。首先确定矩阵的尺寸。我想用0之间的数字随机填充矩阵[ m ][ n ]。。10。然后创建另一个相同尺寸的矩阵，并用 -1 s (最终矩阵)填充它。然后迭代初始矩阵，看看是否会达到0。当您点击位置(x，y)时，转到最终的矩阵，用0填充行 x，用0填充列 y。 在结束时读取最终矩阵，如果值为 -1(原始值) ，则将初始矩阵的相同位置的值复制到最终。

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;
}

这是我的解决办法。从代码中可以看到，给定一个 M * N 矩阵，一旦它检查该行中的一个零，它就会将整行设置为零。我的解的时间复杂度为 O (M * N)。 我共享了整个类，它有一个静态填充的数组用于测试，还有一个显示数组方法用于在控制台中查看结果。

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("");
}


}

}

One Pass-我只遍历了一次输入，但是使用了一个新的数组和两个额外的布尔变量。

public static void main(String[] args) {


Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();


boolean rowDel = false, colDel = false;
int arr[][] = new int[n][n];
int res[][] = new int[n][n];
int i, j;
for (i = 0; i < n; i++) {


for (j = 0; j < n; j++) {
arr[i][j] = sc.nextInt();
res[i][j] = arr[i][j];
}
}


for (i = 0; i < n; i++) {


for (j = 0; j < n; j++) {
if (arr[i][j] == 0)
colDel = rowDel = true; //See if we have to delete the
//current row and column
if (rowDel == true){
res[i] = new int[n];
rowDel = false;
}
if(colDel == true){
for (int k = 0; k < n; k++) {
res[k][j] = 0;
}
colDel = false;
}


}


}


for (i = 0; i < n; i++) {


for (j = 0; j < n; j++) {
System.out.print(res[i][j]);
}
System.out.println();
}
sc.close();


}

设置一个标志(这里我使用 -1) ，然后一旦我们改变所有匹配的行和 coll，替换所有标志为零

public class Main {


public static void main(String[] args) {




//test case 1
int[][] multi = new int[][]{
{ 1, 2, 3 },
{ 4, 0, 5 },
{ 0, 6, 7 },
};


//test case 2
int[][] multi2 = new int[][]{
{ 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},
};


TwoDArraySetZero(multi2);
}






static  void  TwoDArraySetZero(int[][] array){


//iterate through all elements
for(int i = 0 ; i <= array.length-1 ; i++){
for (int j = 0; j <= array.length-1; j++) {


//checking if match with zero
if (array[i][j] == 0){


//set replace with -1 all matching zero row and col if not zero
for (int k = 0; k <= array.length-1 ; k++) {
if(array[i][k] != 0 )
array[i][k] = -1;
if(array[k][j] != 0)
array[k][j]= -1;
}
}
}
}




//print array
for(int i = 0; i <= array.length-1; i++)
{
for(int j = 0; j <= array.length-1; j++)
{
//replace with zero all -1


if(array[i][j] == -1)
array[i][j] = 0;


System.out.printf("%5d ", array[i][j]);
}
System.out.println();
}


}


}