1. 題目

編寫一種算法，若M × N矩陣中某個元素為0，則將其所在的行與列清零。

示例 1： 輸入： [[1,1,1],[1,0,1],[1,1,1] ] 輸出： [[1,0,1],[0,0,0],[1,0,1] ]示例 2： 輸入： [[0,1,2,0],[3,4,5,2],[1,3,1,5] ] 輸出： [[0,0,0,0],[0,4,5,0],[0,3,1,0] ]

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/zero-matrix-lcci
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 將是否刪除的信息，存儲在第一行，第一列
• O(1) 空間復雜度

class Solution { public:void setZeroes(vector<vector<int>>& matrix) {if(matrix.size()==0 || matrix[0].size() == 0)return;//先遍歷除第一行，第一列外的區域int i, j, m = matrix.size(), n = matrix[0].size();bool r0c0Zero = (matrix[0][0] == 0);bool r0 = 0, c0 = 0;if(!r0c0Zero){for(i = 1; i < m; i++)if(matrix[i][0] == 0){c0 = true;//第一列需要后序變0break;}for(j = 1; j < n; j++)if(matrix[0][j] == 0){r0 = true;//第一行需要后序變0break;}}for(i = 1; i < m; i++)for(j = 1; j < n; j++){if(matrix[i][j] == 0){matrix[0][j] = 0;//用第一行標記是否刪除列matrix[i][0] = 0;//用第一列標記是否刪除行}}for(i = 1; i < m; i++){if(matrix[i][0] == 0)//刪除行for(j = 1; j < n; j++)matrix[i][j] = 0;}for(j = 1; j < n; j++){if(matrix[0][j] == 0)//刪除列for(i = 1; i < m; i++)matrix[i][j] = 0;}if(r0c0Zero)//刪除第一行，第一列{for(i = 1; i < n; i++)matrix[0][i] = 0;for(i = 1; i < m; i++)matrix[i][0] = 0;}else{if(r0)//刪除第一行{for(j = 0; j < n; j++)matrix[0][j] = 0;}if(c0)//刪除第一列{for(i = 0; i < m; i++)matrix[i][0] = 0;}}} };

總結

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 01.08. 零矩阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。