描述如下:
有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里面集成有函数,请指出函数名称。谢谢。
有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里面集成有函数,请指出函数名称。谢谢。
不知道我理解是否正确。
0,1,1,0
1,0,0,1
1,1,1,1
1,0,1,1B1
1,1,0
0,0,1
1,1,1B2
0,1,1
1,0,0
1,1,1这种情况满足A交B1=B1 A交B2=B2吗?我的理解应该是满足
方法一:
暴力法,M*N的矩阵中只有(X+1)*(Y+1)个(M-X)*(N-Y)的子矩阵对吧,依次暴力枚举就行了,判断有没有一个是合适的方法二:
用KMP算法对
对M*N的矩阵中的第一行开始,依次判断(M-X)*(N-Y)中的第一行在不在里面(KMP算法非常快)
如果不在,说明M*N矩阵的第一行肯定用不上,此时只需要对剩下的(M-1)*N来同样处理,反之如果在里面,你就知道对齐的位置了对吧,你根据这个对齐的位置依次往下比较,如果全部相等,就找到了,否则同样地说明了第一行肯定用不上。
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
}
这样描述 你看行么?A交B1=B1,A交B2=B2,A交B3!=B3,意思就是说,说是交集,其实也就是包含的意思,即:A要么包含B1,要么不包含B1。如果A和B1的交集是B1的一个子集的话,就可以认定其不符合要求。那么直接可丢弃掉。 在总结一次:求在矩阵A中是否完整存在矩阵B1,B2,B3。 呵呵,就这么个意思。
bool[,] b1 = new bool[3, 3] { { false, true, false }, { false, true, false }, { false, true, false } };
//bool[,] b2 = new bool[3, 3] { { false, true, false }, { false, true, false }, { false, true, false } };
//bool[,] b3 = new bool[3, 3] { { false, true, false }, { false, true, false }, { false, true, false } };
bool isfind = false;
unsafe
{
fixed (bool* pa = &a[0, 0])
fixed (bool* pb = &b1[0, 0])
{
B3* pb3 = (B3*)pb;
bool* pa1 = pa;
for (int x = 0; x <= 5 - 3; x++)//5-3表示a和b1的第二纬长度之差
{
for (int y = 0; y <= 6 - 3; y++)//6-3表示a和b1的第一纬长度之差
{
if (isfind = ((B3*)pa1)->Equals(*pb3))
{
bool* pa2 = pa1;
for (int i = 0; i < 2; i++)
{
pa2 += 6;//6为二维数组a的第一纬长度
if (!(isfind = ((B3*)pa2)->Equals(*pb3)))
{
break;
}
}
}
if (isfind)
break;
pa1++;
}
if (isfind)
break;
pa1 += 3;//3为二维数组b1的第一纬长度
}
}
}
Console.WriteLine(isfind);
Console.ReadLine();自定义结构体,用户封装子集单行信息,进行快速比较,子集第一纬度的长度决定了这个结构体内bool类型字段的数目。public struct B3
{
bool tmp1;
bool tmp2;
bool tmp3;
}