問題描述

給定一個 m x n 的矩陣，如果矩陣中的某個元素為 0，則需要將其所在的行和列的所有元素都置為 0。要求使用原地算法，即不使用額外的矩陣空間，只允許使用常數級別的額外空間。

示例

示例 1：

輸入：

matrix = [[1, 1, 1],[1, 0, 1],[1, 1, 1]
]

輸出：

[[1, 0, 1],[0, 0, 0],[1, 0, 1]
]

示例 2：

輸入：

matrix = [[0, 1, 2, 0],[3, 4, 5, 2],[1, 3, 1, 5]
]

輸出：

[[0, 0, 0, 0],[0, 4, 5, 0],[0, 3, 1, 0]
]

約束條件

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -2^31 <= matrix[i][j] <= 2^31 - 1

進階要求

1. 一個直觀的解決方案是使用 O(mn) 的額外空間，但這并不是一個好的解決方案。
2. 一個簡單的改進方案是使用 O(m + n) 的額外空間，但這仍然不是最好的解決方案。
3. 能否實現一個僅使用 常量空間 的解決方案？

---

問題分析

本題要求將矩陣中某些行和列置零，且必須使用原地算法。直接遍歷矩陣并將對應行和列置零會導致信息丟失，因此需要一種方法來標記哪些行和列需要被置零。

難點分析

1. 標記零的位置：如何在不使用額外矩陣的情況下記錄哪些行和列需要被置零。
2. 原地修改：在標記完成后，如何在不破壞標記信息的情況下完成置零操作。
3. 第一行和第一列的特殊情況：如果第一行或第一列本身包含零，直接使用它們作為標記可能會導致誤修改。

解題思路

我們可以通過以下步驟實現原地算法：

1. 使用第一行和第一列作為標記：

   • 遍歷矩陣，如果某個元素為 0，則將該元素所在行的第一個元素和所在列的第一個元素置為 0。這樣，第一行和第一列就成為了標記行和列是否需要置零的“索引”。

2. 處理第一行和第一列的特殊情況：

   • 如果第一行或第一列本身存在 0，則需要額外記錄，因為它們會被用作標記，可能會被誤修改。

3. 根據標記置零：

   • 遍歷第一行和第一列的標記，將對應的行和列置零。

4. 處理第一行和第一列：

   • 最后根據之前記錄的特殊情況，決定是否將第一行和第一列整體置零。

---

代碼實現

以下是完整的 C 代碼實現：

void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {int firstRowZero = 0;           // 標記第一行是否需要置零int firstColZero = 0;           // 標記第一列是否需要置零// 檢查第一行是否需要置零for (int j = 0; j < *matrixColSize; j++) {if (matrix[0][j] == 0) {firstRowZero = 1;break;}}// 檢查第一列是否需要置零for (int i = 0; i < matrixSize; i++) {if (matrix[i][0] == 0) {firstColZero = 1;break;}}// 使用第一行和第一列作為標記for (int i = 1; i < matrixSize; i++) {for (int j = 1; j < *matrixColSize; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0;  // 標記該行需要置零matrix[0][j] = 0;  // 標記該列需要置零}}}// 根據標記置零（跳過第一行和第一列）for (int i = 1; i < matrixSize; i++) {for (int j = 1; j < *matrixColSize; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 0;}}}// 處理第一行if (firstRowZero) {for (int j = 0; j < *matrixColSize; j++) {matrix[0][j] = 0;}}// 處理第一列if (firstColZero) {for (int i = 0; i < matrixSize; i++) {matrix[i][0] = 0;}}
}

代碼說明

1. 標記邏輯：

   • 使用第一行和第一列的元素作為標記，記錄哪些行和列需要被置零。

2. 特殊情況處理：

   • 額外記錄第一行和第一列是否需要被置零，因為它們會被用作標記。

3. 置零操作：

   • 根據第一行和第一列的標記，將對應的行和列置零。

4. 原地修改：

   • 整個過程只使用了常數級別的額外空間，滿足原地算法的要求。

---

測試用例

以下是幾個測試用例及其結果：

測試用例 1

輸入：

matrix = [[1, 1, 1],[1, 0, 1],[1, 1, 1]
]

輸出：

[[1, 0, 1],[0, 0, 0],[1, 0, 1]
]

測試用例 2

輸入：

matrix = [[0, 1, 2, 0],[3, 4, 5, 2],[1, 3, 1, 5]
]

輸出：

[[0, 0, 0, 0],[0, 4, 5, 0],[0, 3, 1, 0]
]

測試用例 3

輸入：

matrix = [[1, 2, 3, 4],[5, 0, 7, 8],[9, 10, 11, 12]
]

輸出：

[[1, 0, 3, 4],[0, 0, 0, 0],[9, 0, 11, 12]
]

---

總結

本題通過利用矩陣的第一行和第一列作為標記，實現了原地置零的功能。這種方法不僅滿足了原地算法的要求，還具有較高的效率。時間復雜度為 O(m × n)，空間復雜度為 O(1)。