0%

leetcode Set Matrix Zeroes

leetcode Set Matrix Zeroes

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

Follow up:Did you use extra space? A straight forward solution using O(_m__n_) 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?

题目地址:leetcode Set Matrix Zeroes

题目大意: 给定一个矩阵,如果它其中的某个元素为0,那么该元素所在行和所在列均变为0.

思路:

  1. 创建一个矩阵的拷贝,然后根据这个拷贝进行判断O(MN)
  2. 创建一个数组,记录矩阵为0的行和列下标O(m+n)
  3. 把有0的元素映射到首行和首列

 

Python 方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
# @param matrix, a list of lists of integers
# RETURN NOTHING, MODIFY matrix IN PLACE.
def setZeroes(self, matrix):
m , n = len(matrix), len(matrix[0])
temp = [[matrix[i][j] for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
if not temp[i][j]:
self.setZero(i,j,n,m,matrix)

def setZero(self,row,col,n,m,matrix):
for i in range(m):
matrix[i][col]=0
for j in range(n):
matrix[row][j]=0

 

Python 方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
# @param matrix, a list of lists of integers
# RETURN NOTHING, MODIFY matrix IN PLACE.
def setZeroes(self, matrix):
m , n = len(matrix), len(matrix[0])
row , col = [0 for i in range(m)] , [0 for i in range(n)]
for i in range(m):
for j in range(n):
if not matrix[i][j]:
row[i]=col[j]=1
for i in range(m):
if row[i]:
for j in range(n):
matrix[i][j]=0

for j in range(n):
if col[j]:
for i in range(m):
matrix[i][j]=0


 

Python 方法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""

m, n, col0_zero = len(matrix), len(matrix[0]), False
for i in range(m):
if not matrix[i][0]: col0_zero = True
for j in range(1, n):
if not matrix[i][j]:
matrix[i][0] = matrix[0][j] = 0

for i in range(m - 1, -1, -1):
for j in range(n - 1, 0, -1):
if (not matrix[i][0]) or (not matrix[0][j]):
matrix[i][j] = 0
if col0_zero: matrix[i][0] = 0


 

C++方法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
bool col0_zero = false; //第一列是否为0

for(int i = 0; i < matrix.size(); ++i){
if(!matrix[i][0]) col0_zero = true;
for(int j = 1; j < matrix[0].size(); ++j)
if(!matrix[i][j])
matrix[i][0] = matrix[0][j] = 0;
}

for(int i = matrix.size() - 1; i >= 0; --i){
for(int j = matrix[0].size() - 1 ; j >= 1; --j)
if(!matrix[i][0] !matrix[0][j])
matrix[i][j] = 0;

if(col0_zero) matrix[i][0] = 0;
}
}
};
请我喝杯咖啡吧~