清空所有 'bad' 列和行的算法

Question

给定字节矩阵(所有值在内存中都是 1 位)，如果其中至少有一个零，则称其为原始列或“坏”列。查找算法，占用 O(1) 额外内存。

如果没有另一个值(如 -1)或另一个重复矩阵来跟踪已经找到的空值，并且不会将它们误认为是我们填充的空值，我不知道该怎么做。

Answer 1

假设 A 是提供给您的字节矩阵。该解决方案使用恒定的额外空间。使用矩阵中的第一行和第一列作为标志。row1 只需要一个额外的标志(这里是 r1)。

void setZeroes(vector<vector<int> > &A) {
    int m = A.size();
    int n = A[0].size();
    int r1 = 1; //row1
    for(int j = 0; j < n; j++){
        r1 *= A[0][j];
    }
    for(int i = 1; i < m; i++){ //first row skipped
        for(int j = 0; j < n; j++){
            A[0][j] *= A[i][j]; //Marking Colm
            A[i][0] *= A[i][j]; //Marking rows, skipping row#1
        }
    }
    for(int i = 1; i < m; i++){
        for(int j = 1; j < n; j++){
            A[i][j] = A[0][j] * A[i][0];
        }
    }
    //At last, update colm1.
    for(int j = 1; j < m; j++){
        A[j][0] *= A[0][0];
    }
    //At last, update row1.
    for(int j = 0; j < n; j++){
        A[0][j] *= r1;
    }
}