算法 - 在另一个2d数组中查找2d数组的存在

I came across this question while in an interview and i am unable to find the best way to do it.

我在接受采访时遇到了这个问题,我无法找到最佳方法。

The question says, there are two 2d arrays, one is bigger than the other. Lets say,

问题是,有两个2d阵列,一个比另一个大。让我们说,

Array_1 = [[1,2],
           [5,6]]

and

Array_2 = [[1,2,3,4],
           [5,6,7,8], 
           [9,10,11,12]]

Since, here the Array 2 contains Array 1, the algo should return true. Otherwise, false.

因为,这里数组2包含数组1,算法应该返回true。否则,假。

The size of the array can be anything.

数组的大小可以是任何东西。

4 个解决方案

#1

I would fill in the smaller array to the bigger dimensions with null values (or with NaN), convert to 1D and truncate/strip the unnecessary nulls :

我会使用空值(或使用NaN)将较小的数组填充到较大的维度,转换为1D并截断/删除不必要的空值:

array_1 = [1, 2, null, null, 5, 6]
array_2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

then compare the 1D arrays, while skipping the null values - this would be O(n*m) in the worst case (such as [1,1,1,2] vs [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]), and it would be O(n) in the best case (if every number in the bigger array was different)

然后比较1D数组,同时跳过空值 - 在最坏的情况下这将是O(n * m)(例如[1,1,1,2] vs [1,1,1,1,1,1] ,1,1,1,1,1,1,1,1,1,1,1]),在最好的情况下它是O(n)(如果较大数组中的每个数字都不同)

Edit: more logic is needed to ensure comparison only within the complete rows of the bigger array, not across rows...

编辑:需要更多逻辑来确保仅在较大数组的完整行内进行比较,而不是跨行...

I guess you could convert the arrays to dictionaries of positions and figure out a bit more complicated and faster algorithm if you need to do multiple comparisons...

You could also rotate the smaller array if needed, e.g.:

array_1_270 = [6, 2, null, null, 1, 5]

#2

Try this.

function Test() {

var x = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]];
var y = [[6, 7], [10, 12]];

for (i = 0; i < x.length; i++) {
    for (j = 0; j < x[i].length; j++) {
        if (x[i][j] == y[0][0])
            if (findMatch(x, y, i, j)) {
                console.log("Match Found");
                return true;
            }
    }
}
console.log("Not found");
return false;
}


function findMatch(x, y, i, j) {
var b = true;
for (k = i; k < y.length; k++) {
    for (n = j; n < y[k].length; n++) {
        if (y[k - i][n - j] != x[k][n]) {
            b = false;
            break;
        }
    }
}
return b;
}

Note that this doesn't match if the smaller array is rotated inside the big array.(Written in javaScript)

请注意,如果较小的数组在大数组内旋转,则不匹配。(以javaScript编写)

#3

You can try aho-corasick algorithm for 2 dimension. Aho-corasick algorithm is the fastest multiple pattern matching. Here is a similar question:is there any paper or an explanation on how to implement a two dimensional KMP?

您可以尝试2维的aho-corasick算法。 Aho-corasick算法是最快的多模式匹配。这是一个类似的问题:是否有任何关于如何实施二维KMP的论文或解释?

#4

Maybe a little simpler in Python 2.6

在Python 2.6中可能更简单一些

def check():
    small=[[1,2],[5,6]]             #matches upper left corner
    smallrows = len(small)          #rows = 2
    smallcols = len(small[0])       #cols = 2
    big=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
    bigrows = len(big)              #rows = 3
    bigcols = len(big[0])           #cols = 4

    for i in range(bigrows-smallrows+1):        #i is number row steps
        for j in range(bigcols-smallcols+1):    #j is number col steps
            flag = 0
            for k in range(smallrows):
                for l in range(smallcols):
                    if big[i+k][j+l] != small[k][l]:
                        flag = 1
                        continue
            if flag == 0:
                return(True)
    return(False)

print check()

#1