73. Set Matrix Zeroes
题目:
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
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?
代码:
题目很简单,就是矩阵中如果存在值为0的元素,就把该元素对应的行和列上面的元素全都改成0。
思考了半天,还是遍历了两遍,复杂度至少在O(mn):
public void setZeroes(int[][] matrix) {
int i,j;
ArrayList<Integer> row = new ArrayList<Integer>();
ArrayList<Integer> col = new ArrayList<Integer>();
//第一个循环,遍历一遍,记录哪些行和哪些列需要改成0
for (i=0;i < matrix.length;i++)
{
for (j=0;j<matrix[i].length;j++)
{
if(matrix[i][j] == 0)
{
row.add(i);
col.add(j);
}
}
}
//第二个循环,又遍历一遍,根据需要变为0的行和列修改对应元素
for (i=0;i < matrix.length;i++)
{
for (j=0;j<matrix[i].length;j++)
{
if(row.contains(i)||col.contains(j))
{
matrix[i][j] =0;
// System.out.print("修改第"+i+"行,第"+j+"列");
}
}
}
}
题目中提到算法复杂度可以小于 O(m + n),还在研究中...
最新文章
- Greenplum记录(一):主体结构、master、segments节点、interconnect、performance monitor
- JavaScript闭包浅谈
- 在Extjs中对日期的处理,以及在后端数据在SQL语句的判断处理
- 如何为CriteriaOperator过滤对象转换为lambda表达式,即:linq to xpo的动态where语句
- HDU 5937 Equation
- BZOJ 1103: [POI2007]大都市meg
- C# 获取指定接口的所有实现类
- [转] Android应用程序与SurfaceFlinger服务的关系概述和学习计划
- BZOJ_2179_FFT快速傅立叶_(FFT)
- php代码优化技巧
- char与byte差异
- osg蝴蝶纹理
- 关于quotename的用法
- OpenCV读写摄像头并写入视频
- [Swift]LeetCode830. 较大分组的位置 | Positions of Large Groups
- 【php】记录一次生产环境bug的调试
- nginx 出现504 Gateway Time-out的解决方法
- 基于JDK1.8版本的hashmap源码笔记(二)
- Spotlight&#160;on&#160;Mysql在Windows平台下的安装及使用简介
- cocos2d-js 越来越慢的定时器schedule 制作不变慢的定时器