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

题目：有一个矩阵（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)。

-