LeetCode中二維數組如何實現零矩陣

LeetCode中二維數組如何實現零矩陣

在LeetCode中，零矩陣（Zero Matrix）是一個常見的算法問題。給定一個二維數組（矩陣），如果某個元素為0，則將其所在的行和列的所有元素都設置為0。本文將介紹如何實現這一功能。

問題描述

給定一個 m x n 的矩陣，如果矩陣中的某個元素為0，則將其所在的行和列的所有元素都設置為0。要求在原矩陣上進行修改，不使用額外的空間。

解決思路

1. 標記法：

   • 首先遍歷矩陣，找到所有值為0的元素，并記錄它們所在的行和列。
   • 然后再次遍歷矩陣，將標記的行和列中的所有元素設置為0。

2. 原地修改：

   • 使用矩陣的第一行和第一列來記錄是否需要將對應的行或列設置為0。
   • 首先檢查第一行和第一列是否需要設置為0。
   • 然后遍歷矩陣的其他部分，如果某個元素為0，則將其所在的行和列的第一個元素設置為0。
   • 最后根據第一行和第一列的標記，將對應的行和列設置為0。

代碼實現

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
    
    # 使用第一行和第一列來標記
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    
    # 根據標記設置0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    
    # 處理第一行和第一列
    if first_row_has_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_has_zero:
        for i in range(m):
            matrix[i][0] = 0

總結

通過使用矩陣的第一行和第一列來記錄需要設置為0的行和列，我們可以在不使用額外空間的情況下實現零矩陣。這種方法的時間復雜度為O(m*n)，空間復雜度為O(1)，是一種高效的解決方案。