【题目】
原文:
1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.
译文:
写一个函数处理一个MxN的矩阵,如果矩阵中某个元素为0,那么把它所在的行和列都置为0.
【分析】
【思路一】
遍历一次矩阵,当遇到元素等于0时,记录下这个元素对应的行和列。 可以开一个行数组row和列数组col,当元素a[i][j]等于0时, 就把row[i]和col[j]置为true。第二次遍历矩阵时,当某个元素对应的行row[i] 或列col[j]被设置为true,说明该元素在需要被置0的行或列上,因此将它置0。
【思路二】
想要常数空间,可以复用第一行和第一列作为辅助空间使用。不用开辟新的存储空间。其实第一行和第一列所在数组就是思路1中设置的数组,这样减少空间开销。
1.先确定第一行和第一列是否需要清零即,看看第一行中是否有0,记下来。也同时记下来第一列中有没有0。
2.扫描剩下的矩阵元素,如果遇到了0,就将该行第一个元素和该列第一个元素赋值为0即赋值第一行数组和第一列数组。
这里不用担心会将本来第一行或第一列的1改成了0,因为这些值最后注定要成为0的。
3.根据第一行和第一列的信息,已经可以将剩下的矩阵元素赋值为结果所需的值了即,拿第一行为例,如果扫描到一个0,就将这一列都清0。
4.根据1中确定的状态,处理第一行和第一列。如果最开始得到的第一行中有0的话,就整行清零。同理对列进行处理。
【代码一】
/*********************************
* 日期:2014-05-15
* 作者:SJF0115
* 题目: Set Matrix Zeroes
* 来源:CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
void SetMatrixZeroes(int **matrix,int m,int n){
int i,j;
//初始化
int* col = new int(n+1);
int* row = new int(m+1);
memset(col,0,sizeof(int)*(n+1));
memset(row,0,sizeof(int)*(m+1));
//寻找0
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
if(matrix[i][j] == 0){
row[i] = col[j] = 1;
}//if
}//for
}//for
//0所在列和行全置为0
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
if(row[i] || col[j]){
matrix[i][j] = 0;
}//if
}//for
}//for
}
int main(){
int m,n,i,j;
//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d%d",&m,&n) != EOF){
if(m == 0 || n == 0){
break;
}
//初始化
int** matrix = new int*[m];
for(i = 0;i < m;i++){
matrix[i] = new int[n];
}
//输入
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cin>>matrix[i][j];
}
}
//置0
SetMatrixZeroes(matrix,m,n);
//输出
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
【代码二】
/*********************************
* 日期:2014-05-15
* 作者:SJF0115
* 题目: Set Matrix Zeroes
* 来源:CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
//Set Matrix Zeroes
void SetMatrixZeroes(int **matrix,int m,int n){
int i,j;
int firstRow = 0;
int firstCol = 0;
//判断第一行是否有0
for(i = 0;i < n;i++){
if(matrix[0][i] == 0){
firstRow = 1;
}
}//for
//判断第一列是否有0
for(i = 0;i < m;i++){
if(matrix[i][0] == 0){
firstCol = 1;
}
}//for
//搜索0进行标记
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
if(matrix[i][j] == 0){
matrix[i][0] = 0;
matrix[0][j] = 0;
}//if
}//for
}//for
//根据第一行和第一列把剩余元素进行置零
for(i = 1;i < m;i++){
for(j = 1;j < n;j++){
if(matrix[i][0] == 0 || matrix[0][j] == 0){
matrix[i][j] = 0;
}//if
}//for
}//for
//第一行存有0则全设置为0
if(firstRow){
for(i = 0;i < n;i++){
matrix[0][i] = 0;
}
}//if
//第一列存有0则全设置为0
if(firstCol){
for(i = 0;i < m;i++){
matrix[i][0] = 0;
}
}//if
}
int main(){
int m,n,i,j;
freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
while(scanf("%d%d",&m,&n) != EOF){
if(m == 0 || n == 0){
break;
}
//初始化
int** matrix = new int*[m];
for(i = 0;i < m;i++){
matrix[i] = new int[n];
}
//输入
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cin>>matrix[i][j];
}
}
//置0
SetMatrixZeroes(matrix,m,n);
//输出
for(i = 0;i < m;i++){
for(j = 0;j < n;j++){
cout<<matrix[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
分享到:
相关推荐
试用Zeros2.2.3 博文链接:https://corelengine.iteye.com/blog/230268
Zeros Pascal Triangle Next Permutation Inversion of Array (Using Merge Sort) Stock Buy and Sell Rotate Matrix 第3天:(数学) Excel 列号 在 log N 中查找 n^x 在数字的阶乘中计算尾随零 在 Log N 网格中...
前端开源库-count-trailing-zeros计数尾随零,计数二进制整数的尾随零的数目。
例子 var mvp = require ( "ndarray-matrix-vector-product" )var zeros = require ( "zeros" )//Initialize some vectors and a matrixvar x = zeros ( [ 16 ] )var M = zeros ( [ 16 , 8 ] )var y = zeros ( [ 8 ]...
ice中间件,可以用来开发,eclipse开发集成环境中可以
ZerOS-bmp存放一些图片-boot系统启动所需的各种固件和配置-docs文档-外部外部依赖库,如csud usb控制模块-包括头文件-src源文件-对象生产的OBJ文件-kernel.disasm对应的汇编-kernel.elf生成的elf文件-kernel.img ...
Inputs: [AorV] Either A or V where A is a NxN adjacency matrix, where A(I,J) is nonzero if and only if an ... I have solved this issue by using NaNs in the table rather than a sparse matrix of zeros.
Zeros and zero dynamics Ch4.pdf
用法:zeros(shape, dtype=float, order=’C’) 返回:返回来一个给定形状和类型的用0填充的数组; 参数:shape:形状 dtype:数据类型,可选参数,默认numpy.float64 dtype类型: t ,位域,如t4代表4位 b,布尔值,true...
HJ Ryser __Combinatorl propertiesof matricesof zeros and ones.pdfHJ Ryser __Combinatorl propertiesof matricesof zeros and ones.pdf
// Create a 2 x 3 matrix. m := dense . New ( 2 , 3 )( 0 , 1 , 2 , 3 , 4 , 5 , ) 要创建零矩阵,请调用dense.Zeros 。 // Create a 2 x 3 zero matrix. m := dense . Zeros ( 2 , 3 ) 运作方式 加减法 用...
N = 23; % filter order, odd better ... % impulse response coefficient matrix magresp = zeros(Nfil,Npt); phasdel = zeros(Nfil,Npt-1); xvec=zeros(Nfil,1); % fractional delay vector P = 2; % po
f1zeros(size(f0)).pdf
Because there is 2 *tail* zeros in number 3628800重要的! 不要尝试计算阶乘! 首先-您将无法获得大数字的确切答案。 第二-计算大整数可能需要花费数年的时间! 尝试不用这种计算就可以考虑出您的出色解决方案。...
logprobs.new_zeros(logprobs.size()) pytorch 0.4版本中用到的 新建一个与logprobs类型相同的Variable 转换为pytorch0.2等版本 logprobs.new(logprobs.size()).zero_() 以上这篇new_zeros() pytorch版本的转换...
$ npm install --save leading-zeros 用法 var leadingZeros = require ( 'leading-zeros' ) ; // arguments -> (number, amount of zero to be prepended) leadingZeros ( 48 , 5 ) ; // => '0000048' ...
ndarray.zeros的替代ndarray.zeros (在 1.0.0 中已删除) 例子 var zeros = require ( "zeros" ) //Creates a 64x64 ndarray over a float64array filled with 0 var x = zeros ( [ 64 , 64 ] ) 它还接受文档中...
例程 2.1-1 L=zeros(7,6);L(2:6,2:3)=1;L(5:6,4:5)=1; c=chaincode4(L); 例程 2.2-2 L=zeros(7,6);L(2:6,2:3)=1;L(5:6,4:5)=1; c=chaincode8(L); 例程 2.2-3 直接运行
ZerOS的 目标 该项目的目标是创建一个在完全模块化内核上运行的OS。 除了必要的系统设置外,所有内容都将作为模块加载。 内核本身没有其他内置功能。