首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >快速2d数组包含2d数组

快速2d数组包含2d数组
EN

Stack Overflow用户
提问于 2015-06-05 17:58:20
回答 1查看 112关注 0票数 2

实现一个2d数组包含另一个数组的好方法是什么?

例:

代码语言:javascript
运行
复制
A = [0, 0, 0]
    [1, 1, 2]
    [0, 3, 4]

B = [1, 2]
    [3, 4]

C = [0, 0, 0]
    [1, 1, 2]

D = [1, 1, 2]
    [9, 3, 4]

contains(A, B) // true
contanis(A, C) // true
contains(A, D) // false

我试过这么做。基本上,它只是遍历A直到Arow == B,如果它找到了一个,然后从行中将A与B进行比较。

代码语言:javascript
运行
复制
public static boolean contains(int[][] a, int[][] b) {

    // search for matching first element
    // only want to search up to a-b size
    for(int ra = 0; ra <= a.length - b.length; ra++) {
        for(int ca = 0; ca <= a[0].length - b[0].length; ca++) {

            // found matching first element
            if(a[ra][ca] == b[0][0]) {
                boolean tempFound = true;

                // check matching array from starting element
                for(int rb = 0; rb < b.length; rb++) {
                    for(int cb = 0; cb < b[0].length; cb++) {
                        if(b[rb][cb] != a[ra + rb][ca + cb]) {
                            tempFound = false;
                            break;
                        }
                    }
                    if(!tempFound) break;
                }

                // found it
                if(tempFound) return true;

                // otherwise keep trying to find first matching element
            }

        }
    }

    return false;

}

但这似乎是令人难以置信的复杂和野蛮的事情,似乎可以用一种更简单的方式。有更好的方法吗?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-06-05 18:04:22

最基本的术语..。您本质上是在执行子字符串搜索,除非您有整数而不是字符,并且没有按顺序对数组进行寻址。因此,将这个问题归结为子字符串搜索算法。

使用稍加修改的Boyer搜索算法,您将获得更好的性能。把它想象成一种二维Boyer Moore搜索算法。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30672950

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档