73.SetMatrixZeroes(medium)
描述
Given a m × n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up: Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
分析
O(mn)空间复杂度
这种方法最简单粗暴,直接克隆一个和matrix等大的二维数组,然后先逐行后逐列扫描,当遇到0设置新matrix的行或者列为0,最后将克隆matrix复制给原matrix即可
O(m+n)空间复杂度
创建长度为m的一维数组缓存matrix各行中是否有0,创建长度为n的一维数组缓存matrix各列中是否由0,最后更新matrix。ps:根据数组缓存各行各列是否存在0很容易由O(m+n)的空间复杂度联想到,但缓存的方式也不一定要使用数组,如(i, j)这样的数值对也很容易联想到Map,以行为key,列为value,但是注意value值覆盖问题(2行1列和2行3列会相互覆盖,需要使用一个LinkedList作为value解决覆盖)
常量空间复杂度
常量空间的方式只是将缓存的信息放在了原matrix中,巧妙利用matrix第一行第一列来缓存matrix各行各列是否有0。
- 先扫描第一行第一列,如果有0,则将各自的flag设置为true
- 然后扫描除去第一行第一列的整个数组,如果有0,则将对应的第一行和第一列的数字赋0
- 再次遍历除去第一行第一列的整个数组,如果对应的第一行和第一列的数字有一个为0,则将当前值赋0
- 然后根据第一行第一列的flag来更新第一行第一列
代码
常量空间算法
public void setMatrixZeroes(int[][] nums){
boolean rowFlag = false;
boolean colFlag = false;
//1.遍历第一行第一列查看是否有0存在
for(int i = 0; i < nums[0].length; i++){
if(nums[0][i] == 0){
//第一行有0存在
rowFlag = true;
}
}
for(int i = 0; i < nums.length; i++){
if(nums[i][0] == 0){
//第一列有0存在
colFlag = true;
}
}
//2.遍历第一行第一列之外的数组查看是否有0存在
for(int i = 1; i < nums.length; i++){
for(int j = 1; j < nums[i].length; j++){
if(nums[i][j] == 0){
//对应的第一行和第一列的数字赋0
nums[0][j] = 0;
nums[i][0] = 0;
}
}
}
//3.遍历第一行第一列之外的数组,如果相应的第一行第一列有0存在,则设置为0
for(int i = 1; i < nums.length; i++){
for(int j = 1; j < nums[i].length; j++){
if(nums[0][j] == 0 || nums[i][0] == 0){
nums[i][j] = 0;
}
}
}
//4.根据第一行第一列的flag来更新第一行第一列
if(rowFlag){
for(int i = 0; i < nums[0].length; i++){
nums[0][i] = 0;
}
}
if(colFlag){
for(int i = 0; i < nums.length; i++){
nums[i][0] = 0;
}
}
}