黑马程序员技术交流社区

标题: 下面算法怎么优化？求解 [打印本页]
作者: 14900    时间: 2014-2-24 17:15
标题: 下面算法怎么优化？求解
有一个矩阵（10*10），元素值只能为0或1，现在写一个函数判断一下有没有一行都为1，且有一列都为0（除了该行的这个元素为1外）；

我当时写了个算法：但效率不高，需要优化，请大虾帮忙优化一下
bool F(int [10][10]input)
{
        for(int i=0;i<10;i++)
        {
                int j;
                for(j=0;j<10;j++)
                        if(input[i][j]==0) break;
                if(j==10)
                {
                        for(int m=0;m<10;m++)
                        {
                                for(int n=0;n<10;n++)
                                        if(input[n][m]==1&&n!=i) break;
                                if(n==10)
                                        return true;
                        }
                }
        }
        return false;
}
目前，要求优化该算法，让程序只需要扫描该矩阵一遍，即可得出结果。
作者: 丶小天    时间: 2014-2-24 18:41
  1. bool F( int [ 10 ][ 10 ] input )
  2. {
  3.     int nRowAllOne = 0;
  4.     int nColAllZero = 0;
  5.     int nColAllZeroTemp = 0;

  7.     for( int i=0; i < 10; i++ )
  8.     {
  9.         int sumRow = 0;
  10.         int j;
  11.         for( j = 0; j < 10; j++ )
  12.         {
  13.             if( 0 < i )//从第二行开始，把元素值都加到第一行对应元素中
  14.             {
  15.                 input[ 0 ][ j ] += input[ i ][ j ];
  16.             }
  17.             sumRow += input[ i ][ j ];//把当前列每个元素加到变量
  18.             if( 9 == i )//当前为最后一行，也已经加到第一行了
  19.             {
  20.                 //加过有列为整列和为全部是1的行数且该元素是0，则认为i该列除了那几个1之外都是0
  21.                 if( nRowAllOne == input[ 0 ][ j ] && 0 == input[ i ][ j ] )
  22.                 {
  23.                     nColAllZero++;
  24.                 }
  25.                 //加过有列为整列和为全部是1的行数+1且该元素是1，则暂时认为i该列除了那几个1之外都是0
  26.                 else if( nRowAllOne + 1 == input[ 0 ][ j ] && 1 == input[ i ][ j ] )
  27.                 {
  28.                     nColAllZeroTemp++;
  29.                 }
  30.             }
  31.         }
  32.         if( 10 == sumRow )//行全部元素和为4则该行全部都是1
  33.         {
  34.             nRowAllOne++;//有行全为1
  35.             if( 9 == i )//最后一行全都是1，则暂时认为的全部为0也都是
  36.             {
  37.                 nColAllZero += nColAllZeroTemp;
  38.             }
  39.         }
  40.     }

  42.     //如果有多行都是1，则
  43.     if( 0 < nRowAllOne && 0 < nColAllZero )//至少有一行都为1，且有一列都为0（除了该行的这个元素为1外）
  44.     {
  45.         return true;
  46.     }
  47.     return false;//没有
  48. }
复制代码




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2