將所有列和行標記爲零

Question

這是一個訪問問題：在一個大小爲mxn的二維數組中，對於每個值爲零的元素，將該元素所在的整個行和列設置爲零，其餘元素不變。

我可以琢磨的方式是迭代數組中的每個元素，並且每次遇到零時，我用零標記整個行和列。但這是天真的，請提出任何改進建議。

Answer 1

如果允許多餘的空間。只需維護兩個標誌陣列。

一個代表行，另一個代表列。所有默認值設置爲1.

掃描您的原始矩陣，假設您在行x和列y中找到0。只需設置row [x] = 0;和列[y] = 0;

然後掃描您的矩陣再次

for (int i = 0; i < height; ++i) 
    for (int j = 0; j < width; ++j) 
    M[i][j] = M[i][j] * row[i] * column[j]; 

然後你得到你的矩陣M改變

Answer 2

如果您隨身攜帶，您將在您找到的第一行之後清除每一行和每列。在清零行和列之前，只需查找並記錄所有的零。或者，創建一個二維數組的副本並修改第二個，同時查看第一個參考。

Answer 3

算法的複雜性是二次的。如果整個矩陣最初都是零，則會擦除每列n_rows次和每行n_columns次。

更好的方法是維護大小爲m和n的布爾值數組，指示哪些行和列需要歸零。遍歷矩陣的元素，適當地填充布爾數組。完成後，根據您在其中找到的值，遍歷布爾數組並填零。這樣，每個元素最多被清零兩次。

Answer 4

允許多餘的空間？如果是這樣，給定mxn矩陣，我們維護兩個位圖，其中一行的大小爲m，以指示行應該歸零的時間，以及類似的列。位圖使得檢查O（1）是否已經設置的行或列變得非常容易。通過1：矩陣的優化迭代，當遍歷矩陣的元素尋找零點時，當我們發現零點是位置（i，j）時，我們可以在兩個位圖中設置相應的位並停止迭代該行以獲取更多元素。 （畢竟我們正在調整整個行和列）。通過2：現在我們有兩個位圖，通過它們遍歷行和列的歸零。如果你想使得非常優化（如果調零是一個昂貴的操作），同時對一行中的元素進行調零，如果設置了相應的列位，則可以跳過該位，在遍歷列時最終歸零。

編輯： 你可以一次完成，只需要一個單獨的位圖，當遍歷矩陣，如果你找到一個零，將整個行和列設置爲零，設置列位圖位置和繼續下一行。在迭代後續行時跳過設置了位的列

Answer 5

package helloWorld; 
import java.util.HashMap; 
import java.util.Map; 

public class Solution { 

    public static int[][] myFunction(int[][] matrix) { 

     // find all rows and columns that contains zeros 
     // keep their indexes in hashMap 
     // loop over the matrix and check if you have row and column in your 
     // hashmap if yes make them zero, and also mark the row/column as 
     // already zeroed 

     Map<String, Boolean> map = new HashMap<String, Boolean>(); 
     int length = matrix[0].length; 
     int heigth = matrix.length; 
     for (int i = 0; i < heigth; i++) { 
      for (int j = 0; j < length; j++) { 
       if (matrix[i][j] == 0) { 
        // mark and keep Row in Map 
        if (!map.containsKey("R" + i)) { 
         map.put("R" + i, false); 
        } 
       // mark and keep column in Map 
       if (!map.containsKey("C" + j)) { 
        map.put("C" + j, false); 
        } 
       } 
      } 
     } 
     for (int i = 0; i < length; i++) { 
      //check if row need to be zeroed and if yes zero it and Mark it  
      //as done 
      if (map.containsKey("R" + i) && !map.get("R" + i)) { 
       for (int j = 0; j < length; j++) { 
        matrix[i][j] = 0; 
       } 
       map.put("R" + i, true); 
      } 
      //check if column need to be zeroed and if yes zero it and Mark 
      //it as done 
      if (map.containsKey("C" + i) && !map.get("C" + i)) { 
       for (int j = 0; j < heigth; j++) { 
        matrix[j][i] = 0; 
       } 
       map.put("C" + i, true); 
      } 
     } 

     return matrix; 
    } 

    public static void main(String[] args) { 

     int[][] matrix = { { 1, 2, 0, 7, 6 }, { 1, 0, 8, 7, 5 }, { 1, 2, 1, 
     7,-1 }, { 1, 2, 3, 4, 0 } }; 
     print(matrix); 
     System.out.println("#####################################"); 
     matrix=myFunction(matrix); 
     print(matrix); 
    } 

    public static void print(int[][] matrix) { 
     int h = matrix.length; 
     int l = matrix[0].length; 

     for (int i = 0; i < h; i++) { 
      for (int j = 0; j < l; j++) { 
       System.out.print(" " + matrix[i][j] + " "); 
      } 
      System.out.println(); 
     } 
    } 
}