日期:2014-05-18  浏览次数:20929 次

求教 2个二维矩阵取交集的精简算法
描述如下:
   
  有2类矩阵,维度各不同:(N,M,x,y均为大于3的自然数)
  1、矩阵A 大小为N*M。
  2、矩阵B1,B2,B3 大小为(N-x)*(M-y)

  如何能快速找出 A交B1=B1 或者A交B2=B2 或者A交B3=空呢?

  给出思路就行,如果.net里面集成有函数,请指出函数名称。谢谢。


------解决方案--------------------
探讨
只判断存在性。 只要能判断出A中是否含有B1 B2 B3 即可。

------解决方案--------------------
http://www.codeproject.com/Articles/51470/Advanced-Matrix-Library-in-C-NET,看看这个网址。
------解决方案--------------------
楼主,我有两个方法
方法一:
暴力法,M*N的矩阵中只有(X+1)*(Y+1)个(M-X)*(N-Y)的子矩阵对吧,依次暴力枚举就行了,判断有没有一个是合适的

方法二:
用KMP算法对
对M*N的矩阵中的第一行开始,依次判断(M-X)*(N-Y)中的第一行在不在里面(KMP算法非常快)
如果不在,说明M*N矩阵的第一行肯定用不上,此时只需要对剩下的(M-1)*N来同样处理,反之如果在里面,你就知道对齐的位置了对吧,你根据这个对齐的位置依次往下比较,如果全部相等,就找到了,否则同样地说明了第一行肯定用不上。
------解决方案--------------------
C# code
题:求一个矩阵中最大的二维子矩阵(元素和最大).如:
          1 2 0 3 4
          2 3 4 5 1
          1 1 5 3 0
          中最大的是:  
          4 5
          5 3
          要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码
分析:方法一、这是最容易想到也是最容易实现的方法。遍历矩阵(行迭代器为i,列迭代器为j),以当前遍历到的元素为首a[i,j],计算二维子矩阵的和(sum=a[i,j]+a[i+1,j]+a[i,j+1]+a[i+1,j+1]),并找出和最大的二维矩阵,注意矩阵的最后一行和最后一列不用遍历。时间复杂度为O(i*j)。
实现代码:

void get_max_22Matrix(int *a,int row,int col,int *result)  
//a为原矩阵,row,col指a矩阵的行和列,result存储最终得到的子二维矩阵  
{  
  int maxsum=0,result_i,result_j,sum;  
    
#define a(i,j) *(a+(i)*col+(j))  //用二维的形式表示一维数组,访问需要一定的代价  
#define result(i,j) *(result+(i)*2+(j))  
    
  for(int i=0; i<row-1; i++)  
    for(int j=0; j<col-1; j++)  
      {  
        sum = a(i,j)+a(i+1,j)+a(i,j+1)+a(i+1,j+1); //访问四个元素并相加得到当前的和  
        if(maxsum<sum) //更新最大子二维矩阵数据  
          {  
            maxsum = sum;  
            result_i = i;  
            result_j = j;  
          }  
      }  
   
   /* 将结果存储到result二维数组中*/  
   result(0,0)=a(result_i,result_j);  
   result(1,0)=a(result_i+1,result_j);  
   result(0,1)=a(result_i,result_j+1);  
   result(1,1)=a(result_i+1,result_j+1);  
#undef a  
#undef result  
}