LeetCode073——矩阵置零
我的LeetCode代码仓：https://github.com/617076674/LeetCode
原题链接：https://leetcode-cn.com/problems/set-matrix-zeroes/description/
题目描述：
知识点：数组
思路一：使用O(m * n)的额外空间
用一个矩阵flag来记录matrix矩阵中0元素所在的位置，再根据flag矩阵来给matrix矩阵置0。
时间复杂度与matrix矩阵中0出现的位置有关，最差情况下的时间复杂度是O(m * n * max(m, n))。空间复杂度是O(m * n)。
JAVA代码：
public class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
if(m == 0){
return;
}
int n = matrix[0].length;
int[][] flag = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(matrix[i][j] == 0){
flag[i][j] = 1;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(flag[i][j] == 1){
for (int k = 0; k < m; k++) {
matrix[k][j] = 0;
}
for (int k = 0; k < n; k++) {
matrix[i][k] = 0;
}
}
}
}
}
}LeetCode解题报告：
思路二：使用O(m + n)的额外空间
这是基于思路一的一个改进。我们其实并不需要知道matrix中每一个0元素的确切位置，我们只需要知道matrix矩阵中哪几行有0元素，哪几列有0元素。我们只需要一个大小为m的数组row来记录哪几行有0元素，另一个大小为n的数组column来记录哪几列有0元素。
时间复杂度是O(m * n)。空间复杂度是O(m + n)。
JAVA代码：
public class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
if(m == 0){
return;
}
int n = matrix[0].length;
int[] row = new int[m];
int[] column = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(matrix[i][j] == 0){
row[i] = 1;
column[j] = 1;
}
}
}
for (int i = 0; i < m; i++) {
if(row[i] == 1){
for (int j = 0; j < n; j++) {
matrix[i][j] = 0;
}
}
}
for (int i = 0; i < n; i++) {
if(column[i] == 1){
for (int j = 0; j < m; j++) {
matrix[j][i] = 0;
}
}
}
}
}LeetCode解题报告：
思路三：使用O(1)的额外空间
如果矩阵matrix的每一行都包含0，我们把整个矩阵都置为 0 。
如果并不是每一行都包含0，基于方案二的思路，我们需要用一些标记来标识某一行或是某一列是否存在 0。其实方案二的思路可以进一步改进。
我们先寻找到一行row，该行不包含0元素。遍历该行中每一个元素对应的每一列，如果该列中包含0，将该行中的该元素置0。
除去第row行外的其他行，如果有包含0的，将这些行均置为0。
对于第row行元素中的0元素，将其对应的列置为0。
这个思路的本质就是将包含0的列的标记记录在了一个不包含0的第row行，而没有使用额外的存储空间。
时间复杂度是O(m * n)。空间复杂度是O(1)。
JAVA代码：
public class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
if(m == 0){
return;
}
int n = matrix[0].length;
//try to find a row without 0
int row = 0;
for (; row < m; row++) {
int column = 0;
for (; column < n; column++) {
if(matrix[row][column] == 0){
break;
}
}
if(column == n){
break;
}
}
if(row == m){
//every row contains 0
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = 0;
}
}
}else{
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(matrix[j][i] == 0){
matrix[row][i] = 0;
}
}
}
//make other row contains 0 to 0
for (int i = 0; i < m; i++) {
if(i == row){
continue;
}
int j = 0;
for (; j < n; j++) {
if(matrix[i][j] == 0){
break;
}
}
if(j < n){
for (int k = 0; k < n; k++) {
matrix[i][k] = 0;
}
}
}
//if a position in the row we select is 0, make its column to 0
for (int i = 0; i < n; i++) {
if(matrix[row][i] == 0){
for (int j = 0; j < m; j++) {
matrix[j][i] = 0;
}
}
}
}
}
}LeetCode解题报告：