ในเมทริกซ์ ถ้าตำแหน่งใดเป็น 0 ให้ทำให้แถวและคอลัมน์นั้นทั้งหมดเป็น 0 in-place (O(1) space)
ตัวอย่าง
Input: [[1,0,1], [1,1,1], [1,1,1]] Output: [[0,0,0], [1,0,1], [1,0,1]]
อัลกอริทึม O(1) Space: ใช้แถวแรกและคอลัมน์แรกเป็น Marker
- เช็คว่าแถวแรกและคอลัมน์แรกมี 0 อยู่แล้วหรือไม่ (flags)
- ใช้เซลล์แรกของแต่ละแถว/คอลัมน์ (matrix[i][0], matrix[0][j]) บันทึกว่าแถว/คอลัมน์นั้นต้อง zero
- Zero ภายในเมทริกซ์ (i>0, j>0) ตาม marker
- Zero แถวแรก/คอลัมน์แรกตาม flags
โค้ด
class Solution:
def setZeroes(self, matrix):
if not matrix:
return
rows, cols = len(matrix), len(matrix[0])
first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
# Use first row/col as markers
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# Zero inner cells based on markers
for i in range(1, rows):
for j in range(1, cols):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# Zero first row/col if needed
if first_row_zero:
for j in range(cols):
matrix[0][j] = 0
if first_col_zero:
for i in range(rows):
matrix[i][0] = 0
# ทดสอบ
mat = [[1,0,1],[1,1,1],[1,1,1]]
sol = Solution()
sol.setZeroes(mat)
for row in mat:
print(row)
# [0, 0, 0]
# [1, 0, 1]
# [1, 0, 1]
ความซับซ้อน
- Time: O(m × n)
- Space: O(1) extra
สรุป
Technique คลาสสิก: ใช้ boundary row/col เป็น marker แทน array เสริม
