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

Given a NxN matrix with 0s and 1s. Set every row that contains a 0 to all 0s and set every column that contains a 0 to all 0s.

给定一个0和1的NxN矩阵。将包含0的每一行设置为0，并将包含0的所有列设置为0。

For example

例如

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

results in

结果

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

A Microsoft Engineer told me that there is a solution that involves no extra memory, just two boolean variables and one pass, so I'm looking for that answer.

一位微软工程师告诉我，有一个解决方案不需要额外的内存，只有两个布尔变量和一个通过，所以我正在寻找那个答案。

BTW, imagine it is a bit matrix, therefore just 1s and 0s are allow to be in the matrix.

顺便说一下，假设它是一个位矩阵，因此只有1和0可以在矩阵中。

30 个解决方案

#1

Ok, so I'm tired as it's 3AM here, but I have a first try inplace with exactly 2 passes on each number in the matrix, so in O(NxN) and it is linear in the size of the matrix.

好的，我很累，因为这里是3，但是我有一个第一个尝试，在矩阵中，每一个数字都是2，所以在O(NxN)中，它是线性的，在矩阵的大小。

I use 1rst column and first row as markers to know where are rows/cols with only 1's. Then, there are 2 variables l and c to remember if 1rst row/column are all 1's also. So the first pass sets the markers and resets the rest to 0's.

我使用1rst列和第一行作为标记，以了解只有1的行/cols在哪里。然后，有两个变量l和c要记住，如果1rst行/列都是1。因此，第一个传递设置了标记，并将其余部分重置为0。

The second pass sets 1 in places where rows and cols where marked to be 1, and resets 1st line/col depending on l and c.

第二遍设置在标记为1的行和cols的位置，并根据l和c重新设置第1行/col。

I doubt strongly that I can be done in 1 pass as squares in the beginning depend on squares in the end. Maybe my 2nd pass can be made more efficient...

我强烈地怀疑，我可以在1个回合中完成，因为在开始的时候，每个方块都取决于最后的方块。也许我的第二关会更有效率……

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)

#2

This cannot be done in one pass since a single bit has an effect on bits before and after it in any ordering. IOW Whatever order you traverse the array in, you may later come accross a 0 which means you have to go back and change a previous 1 to a 0.

这不能在一次传递中完成，因为单个比特在任何排序之前和之后都会对比特产生影响。不管你在数组中遍历了什么顺序，你以后可能会得到一个0，这意味着你必须返回，并将之前的1变为0。

Update

更新

People seem to think that by restricting N to some fixed value (say 8) you can solve this is one pass. Well that's a) missing the point and b) not the original question. I wouldn't post a question on sorting and expect an answer which started "assuming you only want to sort 8 things...".

人们似乎认为通过限制N到某个固定值(比如8)可以解决这个问题。这是a)缺少点和b)而不是原来的问题。我不会发布一个关于排序的问题，并期待一个开始“假设你只想整理8个东西…”的答案。

That said, it's a reasonable approach if you know that N is in fact restricted to 8. My answer above answers the original question which has no such retriction.

这是一个合理的方法如果你知道N实际上被限制为8。我上面的回答回答了最初的问题，这个问题没有这样的问题。

#3

So my idea is to use the values in the last row/column as a flag to indicate whether all of the values in the corresponding column/row are 1s.

因此，我的想法是使用最后一行/列中的值作为标记，以指示对应的列/行中的所有值是否为1。

Using a Zig Zag scan through the entire matrix EXCEPT the final row/column. At each element, you set the value in the final row/column as to the logical AND of itself with the value in the current element. In other words, if you hit a 0, the final row/column will be set to 0. If you it a 1, the value in the final row/column will be 1 only if it was 1 already. In any case set the current element to 0.

使用Zig Zag扫描整个矩阵除了最后一行/列。在每个元素中，您将最终行/列中的值设置为逻辑值，并将其本身与当前元素中的值相匹配。换句话说，如果你到达一个0，最后一行/列将被设置为0。如果它是1，那么最后一行/列中的值将是1，如果它已经是1了。无论如何，将当前元素设置为0。

When you've finished, your final row/column should have 1s iff the corresponding column/row was filled with 1s.

当您完成时，您的最后一行/列应该有1 iff对应的列/行填充了1。

Do a linear scan through the final row and column and looking for 1s. Set 1s in the corresponding elements in body of the matrix where the final row and column are both 1s.

在最后一行和列中做一个线性扫描，然后寻找1。在矩阵的相应元素中设置1，其中最后一行和列都是1。

Coding it will be tricky to avoid off-by-one errors etc but it should work in one pass.

编写代码是很困难的，要避免错误，但是它应该在一个过程中工作。

#4

I've got a solution here, it runs in a single pass, and does all processing "in place" with no extra memory (save for growing the stack).

我在这里有一个解决方案，它只在一个通道中运行，而且所有的处理都是“就地”处理的，没有额外的内存(除了增加堆栈之外)。

It uses recursion to delay the writing of zeros which of course would destroy the matrix for the other rows and cols:

它使用递归来延迟0的书写当然，它会破坏其他行和cols的矩阵:

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

#5

I don't think it's doable. When you're on the first square and its value is 1, you have no way of knowing what the values of the other squares in the same row and column are. So you have to check those and if there's a zero, return to the first square and change its value to zero. I'll recommend doing it in two passes - the first pass gathers information about which rows and columns must be zeroed out (the information is stored in an array, so we're using some extra memory). The second pass changes the values. I know that's not the solution you're looking for, but I think it's a practical one. The constraints given by you render the problem unsolvable.

我不认为这是可行的。当你在第一个方块上，它的值是1时，你无法知道同一行和列中其他方块的值是多少。所以你要检查这些，如果有0，返回到第一个方块，把它的值变成0。我将建议在两个传递过程中执行它——第一个pass收集关于哪些行和列必须为0的信息(信息存储在一个数组中，因此我们使用了一些额外的内存)。第二次传递改变了值。我知道这不是你想要的解决方案，但我认为这是可行的。你所给的约束使问题无法解决。

#6

I can do it with two integer variables and two passes (up to 32 rows and columns...)

我可以用两个整数变量和两个(最多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));

#7

the problem can be solved in one pass

这个问题可以一次性解决。

saving the matrix in an i X j array.

将矩阵保存在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 .

now print all values as 0 for values of i and j saved in a and b rest of the values are 1 ie (3,3) (3,4) (5,3) and (5,4)

现在将所有值都打印为0，对于i和j的值保存在a和b中，其余值为1 ie(3,3)(3,4)(5,3)和(5,4)

#8

Another solution that takes two passes, is to accumulate ANDs horizontally and vertically:

另一个需要两遍的解决方案是水平和垂直地累积。

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    

I thought I could design such an algorithm using parity bits, Hamming codes or dynamic programming, possibly using those two booleans as a 2-bit number, but I've had no success yet.

我想我可以用奇偶校验位、汉明码或动态编程来设计这样一个算法，可能用这两个布尔值作为一个2位数字，但我还没有成功。

Can you please re-check the problem statement with your engineer and let us know? If there is indeed a solution, I want to keep chipping away at the problem.

你能不能和你的工程师重新核对一下问题陈述，让我们知道?如果确实有解决办法，我想继续解决这个问题。

#9

Keep a single variable to keep track of what all of the rows ANDed together are.

保持一个变量来跟踪所有的行在一起的位置。

If a row is -1 (all 1s), then make the next row a reference to that variable

如果一行是-1(所有的1)，那么将下一行作为对该变量的引用。

If a row is anything but, it's a 0. You can do everything in one pass. Psuedo-code:

如果一行是什么，它就是0。你可以一次完成所有的事情。Psuedo-code:

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

That should do it, in a single pass -- but there is an assumption here that N is small enough for the CPU to do arithmetic on a single row, else you're going to need to loop over each row to determine if it's all 1s or not, I believe. But given you're asking about algos and not constraining my hardware, I would just start my answer with "Build a CPU that supports N-bit arithmetic..."

这应该在一个简单的过程中完成，但是这里有一个假设N足够小，可以让CPU在单行上做算术，否则你需要对每一行进行循环，以确定它是否都是1，我相信。但是，如果你问的是algos，而不是限制我的硬件，我会用“构建一个支持n比特算法的CPU…”来开始我的回答。

Here's one example how it can be done in C. Note I argue that values and arr taken together represent the array, and p and numproduct are my iterator and AND product variables use to implement the problem. (I could have looped over arr with pointer arithmetic to validate my work, but once was enough!)

这里有一个例子是如何在c语言中完成的，我认为，值和arr组合在一起表示数组，而p和numproduct是我的迭代器，以及用于实现问题的产品变量。(我可以用指针算法在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;
}

This produces 0, 0, 6, 0, 6, which is the result for the given inputs.

这就产生了0 0 6 0 6，这是给定输入的结果。

Or in PHP, if people think my stack games in C are cheating (I suggest to you that it's not, because I should be able to store the matrix whichever way I please):

或者在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);

Am I missing something?

我遗漏了什么东西?

#10

Nice challange. This solution sort of uses just two booleans created on the stack, but the booleans are created several times on the stack since the function is recursive.

不错的挑战。这个解决方案只使用了在堆栈上创建的两个布尔值，但是由于函数是递归的，所以布尔值在堆栈上被创建了好几次。

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

This scans in a pattern like:

扫描的模式如下:

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

and so on

等等

And then changeing the values in this pattern on return on each of the scan functions. (Bottom up):

然后在每个扫描函数的返回值上改变这个模式的值。(自下而上):

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

and so on

等等

#11

Okay this is a solution that

这是一个解。

• uses just one extra long value for working storage.
• 仅使用一个额外的长值用于工作存储。
• uses no recursion.
• 不使用递归。
• one pass of only N, not even N*N.
• 只有N，甚至N*N。
• will work for other values of N but will need new #defines.
• 将为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;
    }

#12

Actually. If you just want to run the algorithm and print out the results (i.e. not restore them, then this can easily be done in one pass. The trouble comes when you try to modify the array as you're running the algorithm.

实际上。如果您只是想运行该算法并打印出结果(也就是不还原它们，那么这很容易在一次传递中完成)。当你在运行算法时试图修改数组时，麻烦就来了。

Here is my solution It just involves ANDing the rows/columns values for a givein (i,j)'s element and printing it out.

这里是我的解决方案，它只涉及到一个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;
    }
}

#13

I tried to solve this problem in C#.

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

I've used two loop variables (i and j) apart from the actual matrix and n representing its dimension

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

Logic I tried is to:

我尝试的逻辑是:

1. Calculate AND for rows and cols involved in each concentric square of the matrix
2. 计算矩阵的每一个同心方阵中的行和高斯。
3. Store it in its corner cells (I've stored them in anti-clockwise order)
4. 将其存储在其角落的单元格中(我以逆时针顺序存储它们)
5. Two bool variables are used to retain values of two corners when evaluating a particular square.
6. 两个bool变量用于在评估一个特定的正方形时保留两个角的值。
7. This process would end when outer loop (i) is mid way.
8. 当外环(i)是中路时，这个过程就结束了。
9. Evaluate results of other cells based on the corner cells (for rest of i). Skip the corner cells during this process.
10. 根据角细胞(i)对其他细胞的结果进行评估。在此过程中跳过角细胞。
11. When i reaches n, all cells would have its result except for the corner cells.
12. 当我到达n时，除了角细胞外，所有的细胞都会有它的结果。
13. Update the corner cells. This is an extra iteration to length of n/2 other than the single pass constraint mentioned in the problem.
14. 细胞更新的角落。这是一个额外的迭代，长度为n/2，而不是问题中提到的单遍限制。

Code:

代码:

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

#14

While impossible given the constraints, the most space efficient way to do it is by traversing the matrix in an overlaping, alternating row/column fashion, which would make a pattern similar to laying bricks in a zig-zag fashion:

虽然不可能给出约束条件，但最有效的方法是用重叠的、交替的行/列方式遍历矩阵，从而形成类似于以锯齿形的方式铺砖的模式:

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

Using this, you would go in each row/column, as indicated, and if you encounter a 0 at any time, set a boolean variable, and re-walk that row/column, setting the entries to 0 as you go.

使用此方法，您将按指示在每一行/列中执行，如果您在任何时候遇到一个0，则设置一个布尔变量，并重新遍历行/列，将条目设置为0。

This will require no extra memory, and will only use one boolean variable. Unfortunately, if the "far" edge is set to all be 0, that is the worst case and you walk the whole array twice.

这将不需要额外的内存，并且只使用一个布尔变量。不幸的是，如果“far”边缘被设置为0，那么这是最坏的情况，您将遍历整个数组两次。

#15

create a result matrix and set all the values to 1. go through the data matrix as soon as a 0 is encountered, set the result matrix row column to 0

创建一个结果矩阵并将所有值设置为1。当遇到0时，通过数据矩阵，将结果矩阵行列设置为0。

At the end of the first pass, the result matrix will have the correct answer.

在第一轮结束时，结果矩阵将得到正确的答案。

Looks pretty simple. Is there a trick I am missing? Are you not allowed to use a result set?

看起来很简单。我错过了一个小窍门吗?您不允许使用结果集吗?

EDIT:

编辑:

Looks like a F# function, but that is cheating a bit since even though you are doing a single pass, the function can be recursive.

看起来像f#函数，但这有点欺骗，因为即使你在做一个单遍，函数也可以是递归的。

It looks like the interviewer is trying to figure out if you know functional programming.

看起来面试官想知道你是否知道函数式编程。

#16

Well, I came up with a single-pass, in-place (non-recursive) solution using 4 bools and 2 loop counters. I've not managed to reduce it to 2 bools and 2 ints, but I wouldn't be surprised if it was possible. It does around 3 reads and 3 writes of each cell, and it should be O(N^2) ie. linear in the array size.

我用4个bools和2个循环计数器创建了一个单通道、就地(非递归)解决方案。我没有把它减少到2个bools和2个ints，但是如果可能的话，我不会感到惊讶。它大约3读和写的每一个细胞,它应该是O(N ^ 2)ie。数组大小中的线性。

Took me a couple of hours to puzzle this one out - I wouldn't want to have to come up with it under the pressure of an interview! If I've made a booboo I'm too tired to spot it...

我花了几个小时来解决这个问题——我不想在面试的压力下提出这个问题!如果我犯了错误，我太累了，无法发现它……

Um... I'm choosing to define "single-pass" as making one sweep through the matrix, rather than touching each value once! :-)

嗯…我选择将“单通道”定义为使一个遍历矩阵，而不是一次触摸每个值!:-)

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

#17

i hope you enjoy my 1-pass c# solution

我希望你喜欢我的1-pass c#解决方案。

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

您可以使用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
*/

#18

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

1,2布尔值。我只需要假设迭代中的整数索引不算数。

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.

如果我只能确定0是原来的0还是1变成0那么我就不需要用-1了，这样就可以了。

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.

创意的方法是使用上半年行或列的检查,以确定是否包含一个0和下半年设置的值——这是通过观察x width-x然后y和高度y在每个迭代中。根据迭代的上半部分的结果，如果发现行或列中的0，我使用迭代的后半部分将1的值改为-1。

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

我刚意识到这可以用一个布尔值从1到…?

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:

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

#19

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

没有人使用二进制形式?因为它只有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

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)

And the output:

和输出:

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

#20

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

你可以做这样的事情来使用一个pass但是一个输入和输出矩阵:

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.

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

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

然后对输入进行循环。有可能扩大空间效率吗?

#21

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.

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

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.

为了避免添加更多的布尔值，我们正在为矩阵的第一行和列中的行和列存储“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();
}

#22

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.

为了不使用任何额外的空间(不做新矩阵和填充起来,而是直接应用矩阵的变化),矩阵的左上角开始,做团队的计算矩阵(“开始”(0,0))与任何指数>我在考虑任何元素。

hope this works (havent testet)

希望这能起作用(havent testet)

#23

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.)

在c++中测试了不同的N，并且是:一个传递，两个BOOLS，没有递归，没有额外的内存，对于仲裁大的N(到目前为止没有一个解决方案都是这么做的)。

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.

更具体地说，我很有趣两个循环计数器是可以的。我有两个const unsigneds，它只存在，而不是每次都要计算可读性。外环的区间为[0,N]，内环的区间为[1,N - 1]。switch语句在循环中主要存在，以非常清楚地显示它实际上只是一个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:

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

#24

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.

好吧，我意识到这不是一场比赛，但是我用一个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; }
        }
    }
}

#25

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).

你可以在一个通道中完成它——如果你不计算访问矩阵的随机存取顺序，这就消除了单次传递的好处(cache-coherence/内存带宽)。

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

#26

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

#27

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.

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

#28

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.

下面的代码创建了一个大小为m的矩阵。首先确定矩阵的维数。我想把矩阵[m][n]随机地加在0到10之间。然后创建另一个相同维度的矩阵，并将其填充为-1(最终矩阵)。然后遍历初始矩阵，看看是否会达到0。当你点击位置(x,y)时，进入最后一个矩阵，用0和y列填充x。在最后通读最后的矩阵，如果值为-1(原始值)，将初始矩阵的相同位置的值复制到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;
}

#29

here is my solution. 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.

这是我的解决方案。正如您从代码中看到的，给定一个M * N矩阵，当它检查该行中的一个0时，它将整个行设置为零。我的解的时间复杂度是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("");
    }

}

}

}

#30

One Pass - I have traversed the input only once but used a new array and only two extra Boolean variables.

一遍——我只遍历了一次输入，但使用了一个新的数组，并且只使用了两个额外的布尔变量。

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

    }