矩阵格查找的高效求解

G-Spider · 发表于 2011-5-12 18:36:54

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

今天有个同学问了个这个问题，他那里有个程序，跑20*30的矩阵用了14s (四核机)，更大一点的矩阵就基本求不出来，于是就有了这个需求。问题形式是这样的：有一个m*n 的矩阵(m,n 均比较大，比如均100左右，实际需求对于m 会更大， n<200左右) 元素只有4个，｛0，1，2，3｝其中0 表示无意义的值。我们要在其中找到这样的矩阵，满足（矩阵的四个端点，上端与下端相等）如下： a ..........b . . . . . . a..........b 其中a,b ={1,2,3}，a与b可以相等或不等，但不能为0. 并且如果这个大矩阵中有更小的会被包含，不计。找出所有这样的矩阵。例如，下面的查找结果，有两个矩阵：

再看一例，也有两个矩阵满足：

大致就是这个意思，不知道表述清楚了没有，找到的矩阵可以用坐标表示即可。

litaoye · 发表于 2011-5-12 22:17:24

求全解么？还是求m*n的最大解？20 * 30跑14秒有些夸张，全解的话会比较慢，毕竟解的数量可能很多。先统计出来每行1.2.3的坐标的集合，然后依次同后面的行求交集，应该就差不多了。

G-Spider · 发表于 2011-5-13 09:53:01

2# litaoye

求全解。那同学的初步想法是先统计出每列1.2.3的坐标的集合。

gxqcn · 发表于 2011-5-13 10:08:15

我觉得第一步应快速排除“0”的干扰：可将第k行中的“0”全部替换成(k+3)。

G-Spider · 发表于 2011-5-13 10:16:59

4# gxqcn 不会是想做减法运算吧。

zgg___ · 发表于 2011-5-13 11:43:19

假设用最笨的办法，搜索m*n的矩阵中左上角为x*y的满足要求的矩形，计算量小于m*n次。 x和y的选取方式小于m*n种，因此总计算量会小于(m*n)^2次运算。当m和n小于100时，运算量貌似并不是很大。

zeroieme · 发表于 2011-5-15 07:28:40

本帖最后由 zeroieme 于 2011-5-15 10:38 编辑 希哈表，O(n)的复杂度。这里需要m+1个希哈表，所以O(m*n)的复杂度。

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 矩阵格查找的高效求解

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。