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

Question

给定具有0和1的NxN矩阵.将包含a的每一行设置0为all 0s并将包含a的每一列设置0为all 0s.

例如

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

微软工程师告诉我,有一个解决方案不涉及额外的内存,只有两个布尔变量和一个通过,所以我正在寻找答案.

顺便说一句,想象它是一个位矩阵,因此只允许1s和0s在矩阵中.

Answer 1

好吧,所以我很累,因为它在这里是3AM,但是我首先尝试在矩阵中的每个数字上准确地进行2次传递,因此在O(NxN)中它与矩阵的大小呈线性关系.

我使用第一列和第一行作为标记来知道行/列只有1的位置.然后,有2个变量l和c来记住第一行/列是否也都是1.所以第一遍设置标记并将其余部分重置为0.

第二遍在行和列标记为1的位置设置1,并根据l和c重置第一行/列.

我强烈怀疑我可以在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)

Answer 2

这不能在一次通过中完成,因为单个位在任何排序中对其之前和之后的位有影响.IOW无论你通过什么顺序遍历数组,你可能会在0之后遇到,这意味着你必须返回并将之前的1更改为0.

更新

人们似乎认为通过将N限制为某个固定值(比如8),你可以解决这个问题.嗯,这是a)错过了重点,b)不是原来的问题.我不会在排序上发布一个问题,并期望一个答案开始"假设你只想排序8件事......".

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

Answer 3

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

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

完成后,如果相应的列/行填充了1,则最后一行/列应该为1.

在最后一行和一列中进行线性扫描并查找1秒.在矩阵体中的相应元素中设置1,其中最后一行和列都是1.

编写它是很棘手的,以避免一个一个错误等,但它应该在一个通道中工作.

Answer 4

我在这里有一个解决方案,它在一次通过中运行,并且所有处理都"就地"而没有额外的内存(除了增加堆栈).

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

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