Xét một ma trận, nếu một phần tử là 0, thì đặt toàn bộ hàng và cột của ma trận đó thành 0. Chuyển đổi diễn ra tại chỗ (in-place). Ví dụ, nếu ma trận là:
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| 1 | 1 | 1 |
Kết quả sẽ là:
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 0 | 1 |
Các bước:
n := số hàng, m := số cột, flag := false.
Nếu mat[0][0] == 0, flag := true.
row := false, col := false.
Với i từ 1 đến n-1:
- Nếu mat[i][0] == 0, col := True, thoát vòng lặp.
Với i từ 1 đến m-1:
- Nếu mat[0][i] == 0, row := True, thoát vòng lặp.
Với i từ 1 đến n-1, j từ 1 đến m-1:
- Nếu mat[i][j] == 0, đặt mat[i][0] = 0 và mat[0][j] = 0.
Với i từ 1 đến n-1, j từ 1 đến m-1:
- Nếu mat[i][0] == 0 hoặc mat[0][j] == 0, đặt mat[i][j] = 0.
Nếu flag true:
- Với i từ 0 đến n-1, mat[i][0] := 0.
- Với i từ 0 đến m-1, mat[0][i] := 0.
Ngược lại:
- Nếu col true, với i từ 0 đến n-1, mat[i][0] := 0.
- Nếu row true, với i từ 0 đến m-1, mat[0][i] := 0.
Ví dụ
class Solution(object):
def setZeroes(self, matrix):
n = len(matrix)
m = len(matrix[0])
flag = False
if matrix[0][0] == 0:
flag = True
row = False
column = False
for i in range(1, n):
if matrix[i][0] == 0:
column = True
break
for i in range(1, m):
if matrix[0][i] == 0:
row = True
break
for i in range(1, n):
for j in range(1, m):
if matrix[i][j] == 0:
matrix[0][j] = 0
matrix[i][0] = 0
for i in range(1, n):
for j in range(1, m):
if not matrix[i][0] or not matrix[0][j]:
matrix[i][j] = 0
if flag:
for i in range(n):
matrix[i][0] = 0
for i in range(m):
matrix[0][i] = 0
else:
if column:
for i in range(n):
matrix[i][0] = 0
if row:
for i in range(m):
matrix[0][i] = 0
return matrix
ob1 = Solution()
print(ob1.setZeroes([[1,0,1],[1,1,1],[1,1,1]]))
Đầu vào
[[1,0,1],[1,1,1],[1,1,1]]
Đầu ra
[[0, 0, 0], [1, 0, 1], [1, 0, 1]]