算法將空的所有「壞」列和行排除

Question

給定字節矩陣（所有值均爲內存中的1位），如果它至少有一個零，則將其稱爲原始列或列'bad'。查找算法，這需要O（1）額外的內存。

我不知道如何做到這一點，沒有另一個值，如-1或另一個重複的矩陣，跟蹤已發現的空值，而不是用我們填充的空值誤認爲它們。

Answer 1

假設A是提供給您的字節矩陣。該解決方案使用不變的額外空間使用矩陣中的第一行和第列作爲標誌。 只需要一個額外的標誌（此處爲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; 
    } 
} 

Answer 2

該算法使用O（1）空間。以下是步驟：

1. 查找第一行的所有1個值。如果沒有這樣的行，所以所有的行至少包含一個0，所以所有的矩陣都應該變成0。將行的索引保留在變量I.

2. 使用第I行作爲標誌來保留每列的值，即整列的&並存儲在第I行。

3. &每一行，除了第i行和設置值的特定行的元素，即如果它有至少一個0設置整行爲0，否則留下所有1行，第二行等等除了我之外。
4. &對於所有i <> I和j=0,1,...,A[I].length-1，第I行到所有其他行，即A[i][j] &= A[I][j]。

這就是全部！

作爲一個例子，我們有

1 1 1 0 1 0
1 1 1 1 1 1
1 0 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 0

第一步驟後，我們將發現I = 1的第二行。

然後我們正在改變第二行只將基第2步後成爲（它改變了第一，第二，第四和最後一個元素爲0，因爲發現0在列）：

1 1 1 0 1 0
0 0 1 0 1 0
1 0 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 0

在步驟3以後矩陣意願成爲（我們將設置0到具有至少一個0 excep第二行的行）：

0 0 0 0 0 0
0 0 1 0 1 0
0 0 0 0 0 0
1 1 1 1 1 1
0 0 0 0 0 0

後第4步矩陣將成爲繼（我們正在做的通過所有列&操作）：

0 0 0 0 0 0
0 0 1 0 1 0
0 0 0 0 0 0
0 0 1 0 1 0
0 0 0 0 0 0

這就是我們正在尋找的矩陣。