โปรแกรมแปลงค่าในแถวและคอลัมน์เป็นศูนย์สำหรับค่าเป็นศูนย์ในเมทริกซ์ Python

ปัญหา

กำหนดเมทริกซ์ 2D สำหรับแต่ละค่า 0 ในเมทริกซ์ ให้แปลงค่าทั้งหมดในแถวและคอลัมน์นั้นเป็น 0 คืนค่าเมทริกซ์สุดท้าย

ตัวอย่าง: Input matrix มี 0 ที่แถว 0,2,3 และคอลัมน์ 0,1,2 → Output ทุกค่าในแถวและคอลัมน์เหล่านั้นกลายเป็น 0

อัลกอริทึม

1. n = จำนวนแถว, m = จำนวนคอลัมน์
2. สร้าง result matrix res ขนาด n×m เติม 0
3. สร้าง transpose ของเมทริกซ์ต้นฉบับ (เพื่อเข้าถึงคอลัมน์ง่ายขึ้น)
4. วนลูปแต่ละแถว i:
   • ถ้าแถว i ไม่มี 0: วนลูปแต่ละคอลัมน์ j:
     • ถ้าคอลัมน์ j (ใน transpose) ไม่มี 0: res[i][j] = matrix[i][j]
5. คืนค่า res

การนำไปใช้ Python

class Solution:
    def solve(self, matrix):
        n, m = len(matrix), len(matrix[0])
        res = [[0 for _ in range(m)] for _ in range(n)]
        transpose = [list(row) for row in zip(*matrix)]
        
        for i in range(n):
            if 0 not in matrix[i]:
                for j in range(m):
                    if 0 not in transpose[j]:
                        res[i][j] = matrix[i][j]
        return res

# Test
ob = Solution()
matrix = [
    [6, 0, 0, 6, 9],
    [4, 9, 9, 4, 8],
    [0, 8, 3, 4, 2],
    [9, 0, 7, 8, 3],
    [5, 2, 9, 6, 8]
]
print(ob.solve(matrix))

ผลลัพธ์

[[0, 0, 0, 0, 0],
 [0, 0, 0, 4, 8],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 6, 8]]

อธิบาย

• แถว 0, 2, 3 มี 0 → ทั้งแถวกลายเป็น 0
• คอลัมน์ 0, 1, 2 มี 0 → ทั้งคอลัมน์กลายเป็น 0
• เฉพาะเซลล์ที่ไม่อยู่ในแถว/คอลัมน์ที่มี 0 เท่านั้นที่คงค่าเดิม (เช่น [1,3]=4, [1,4]=8, [4,3]=6, [4,4]=8)

ความซับซ้อน

• Time: O(n×m) - ตรวจสอบแต่ละเซลล์คงที่ครั้ง
• Space: O(n×m) - transpose matrix และ result matrix