算法数据结构面试题——标记数组在矩阵特征识别中的应用

题目:有一个矩阵(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;
} 
可见,这个算法在每找到一行元素都是1后,会对整个矩阵进行再扫描,理论上对mxn矩阵操作的时间复杂度为O(mn+mxmxn)=O(mxmxn)。但是考虑到实际情况,肯定是不会到这个上限,但是已经效率很低了。
这时可以考虑,另设一个bool ColAllZero[n]数组,初始为true。在第二层循环中扫描第i行是否都是1时,如果出现该行j列元素为1,即标记ColAllZero[j]为false。
这样只需两层循环,一次扫描,算法如下。
bool F(int [10][10]input) { bool ColAllZero[10]; for(int j = 0; j < 10; j++) ColAllZero[j] = true; for(int i = 0; i < 10; i++) { int j; for(j=0; j < 10; j++) if(input[i][j] == 0) break; if(j < 10) //扫描到[i][j]时发现为0,即不满足要求 { for(int m = 0; m < j; m++) ColAllZero[m] = false; //标记0至j-1列不满足全0 } else //j为10,即扫描完第i行,该行满足要求 { for(int m = 0; m < 10; m++) { if(!ColAllZero[m]) continue; for(int n = 0; n < i - 1; i++) { if(input[n][m] == 1) { ColAllZero[m] = false; break; } } if(n != i - 1) continue; //[n][m]不为0,不满足要求 //否则,m列的0至i-1行满足全0要求 if(i == 9) //满足要求的行号为第9行,即最后一行 return true; //识别结束,为[i][m] for(int n = i + 1; n < 10; i++) //满足要求的行在最后一行之上 { if(input[n][m] == 1) { ColAllZero[m] = false; break; } } if(n == 10) return true; //第i行第m列满足要求 } } } return false; } 
特别注意,虽然该算法仍是三重循环,但分析其时间复杂度就会发现是O(mn),而非O(mmn)或O(mnn)。因为在第二层循环中不满足要求但值为1的元素所在的列都会被ColAllZero标记,这些被标记为false的列在第三重循环中不会再被访问。因此时间复杂度为O(mn)。 
 
-
    原文作者:钟超
    原文地址: https://blog.csdn.net/Poechant/article/details/6231386
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞