程序员面试金典 - 面试题 01.08. 零矩阵

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. 零矩阵的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。