一道微软的面试题：有一个矩阵（10*10）,元素值只能为0或1,现在写一个函数判断一下有没有一行都为1,且有一列都为0（除了该行的这个元素为1外）；我当时写了个算法：但效率不高,需要优
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/18 23:58:15
一道微软的面试题：有一个矩阵（10*10）,元素值只能为0或1,现在写一个函数判断一下有没有一行都为1,且有一列都为0（除了该行的这个元素为1外）；我当时写了个算法：但效率不高,需要优
一道微软的面试题：
有一个矩阵（10*10）,元素值只能为0或1,现在写一个函数判断一下有没有一行都为1,且有一列都为0（除了该行的这个元素为1外）；
我当时写了个算法：但效率不高,需要优化,
bool F(int [10][10]input)
{
for(int i=0;i
一道微软的面试题：有一个矩阵（10*10）,元素值只能为0或1,现在写一个函数判断一下有没有一行都为1,且有一列都为0（除了该行的这个元素为1外）；我当时写了个算法：但效率不高,需要优
bool F( int [ 10 ][ 10 ] input )
{
int nRowAllOne = 0;
int nColAllZero = 0;
int nColAllZeroTemp = 0;
for( int i=0; i < 10; i++ )
{
int sumRow = 0;
int j;
for( j = 0; j < 10; j++ )
{
if( 0 < i )//从第二行开始,把元素值都加到第一行对应元素中
{
input[ 0 ][ j ] += input[ i ][ j ];
}
sumRow += input[ i ][ j ];//把当前列每个元素加到变量
if( 9 == i )//当前为最后一行,也已经加到第一行了
{
//加过有列为整列和为全部是1的行数且该元素是0,则认为i该列除了那几个1之外都是0
if( nRowAllOne == input[ 0 ][ j ] && 0 == input[ i ][ j ] )
{
nColAllZero++;
}
//加过有列为整列和为全部是1的行数+1且该元素是1,则暂时认为i该列除了那几个1之外都是0
else if( nRowAllOne + 1 == input[ 0 ][ j ] && 1 == input[ i ][ j ] )
{
nColAllZeroTemp++;
}
}
}
if( 10 == sumRow )//行全部元素和为4则该行全部都是1
{
nRowAllOne++;//有行全为1
if( 9 == i )//最后一行全都是1,则暂时认为的全部为0也都是
{
nColAllZero += nColAllZeroTemp;
}
}
}
//如果有多行都是1,则
if( 0 < nRowAllOne && 0 < nColAllZero )//至少有一行都为1,且有一列都为0（除了该行的这个元素为1外）
{
return true;
}
return false;//没有
}