Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

Follow up:

A straight forward solution using O(mn) space is probably a bad idea.A simple improvement uses O(m + n) space, but still not the best solution.Could you devise a constant space solution?

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

Constraints:

m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1

難度為中等的題目，給定一個矩陣，把零值所在的行和列都置為零。題目樣例展示的很清楚，所以不再贅述。

題目要求最優方法是把不新建陣列，讓我們看看有什麼方法能用最優方式來解決這個問題。

解題思路：

最簡單的方法就是新建一個矩陣，把原矩陣存在零的行和列都至為0即可，那麼空間複雜度即為O(m*n)。新疆兩個陣列，一個記錄零所在的行，一個記錄零所在的列，那麼空間複雜度即為O(m+n)。

class Solution {    public void setZeroes(int[][] matrix) {         if (matrix.length == 0) {            return;        }               int r = matrix.length; // 計算二維陣列的行長度        int c = matrix[0].length; // 計算二維陣列的列長度              // 定義兩個set，一個記錄零所在的行，一個記錄零所在的列        Set<Integer> row = new HashSet<>();  // 為什麼用HashSet呢？因為Set屬性不能存在重複元素，所以即使行列重複，也避免了冗餘的資料，另外Hashset查詢起來用hashcode，效能也比較好。        Set<Integer> column = new HashSet<>();                for (int i=0; i<r; i++) { //遍歷陣列            for (int j=0; j<c; j++) {                if (matrix[i][j] == 0) { //如果找到為0的元素，分別新增0所在的行和列到各自的set中                    row.add(i);                    column.add(j);                }            }        }                for (int i=0; i<r; i++) {  //再次遍歷陣列            for (int j=0; j<c; j++) {                if (row.contains(i) || column.contains(j)) { //如果set中存在，則至為0                    matrix[i][j] = 0;                }            }        }    }}

最優方案：

這個方案就是用引數陣列來標記，分為四步

1> 分別為第一行和第一列定義兩個boolean變數，之後先分別遍歷第一行和第一列，如果第一行或者第一列有0，則標記對應的boolean變數為true。

2> 開始從陣列下標為1,1的元素開始遍歷剩餘的元素，如果存在0的元素，則把對應的第一行和第一列的元素都至0。

3> 再一次分別遍歷第一行和第一列的元素，如果發現0，則把對應的行和對應的列的元素都至為0.

4> 判斷兩個boolean變數，如果為true，則把為true的第一行或者第一列所有元素都至為0.

這四個步驟可能不容易理解，本質上是定義兩個標記，第一行是否存在0，第一列是否存在0，如果存在則說明第一行或者第一列的所有元素都應該為0.

透過遍歷查詢從第二行和第二列開始的剩餘元素，然後利用改變第一行和第一列中的元素作為驅動，將對應的行和對應的列的值都變為0。

最後在檢視定義的標示來判斷是否將第一行或者第一列全部修改，這裡放到最後的目的是為了不影響其餘元素。

class Solution {    public void setZeroes(int[][] matrix) {        Boolean firstrow = false;        Boolean firstcol = false;        int R = matrix.length;        int C = matrix[0].length;        for (int i = 0; i < R; i++) {            if (matrix[i][0] == 0) {                firstrow=true;                break;            }        }              for (int j=0; j < C; j++) {            if (matrix[0][j] == 0) {                firstcol=true;                break;            }        }                for (int i=1; i<R; i++) {            for (int j=1; j<C; j++) {                if (matrix[i][j] == 0) {                    matrix[i][0] = 0;                    matrix[0][j] = 0;                }            }        }                for (int i=0; i<R; i++) {            if (matrix[i][0] == 0) {                for (int j=0; j<C; j++) {                    matrix[i][j] = 0;                }            }        }                for (int j=0; j<C; j++) {            if (matrix[0][j] == 0) {                for (int i=0; i<R; i++) {                    matrix[i][j] = 0;                }            }        }                if (firstrow) {            for (int i = 0; i < R; i++) {                matrix[i][0] = 0;            }        }                if (firstcol) {            for (int j = 0; j < C; j++) {                matrix[0][j] = 0;            }        }    }}

總結：

這是對二維陣列運用的一種擴充套件，這種利用原始陣列作為引數標示的方式我目前在其他的演算法題上暫時還沒遇到。但是記住這種方式可以再遇到二維陣列對空間複雜度有額外要求是可以有限考慮。