实现一个2d数组包含另一个数组的好方法是什么?
例:
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进行比较。
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;
}
但这似乎是令人难以置信的复杂和野蛮的事情,似乎可以用一种更简单的方式。有更好的方法吗?
发布于 2015-06-05 18:04:22
最基本的术语..。您本质上是在执行子字符串搜索,除非您有整数而不是字符,并且没有按顺序对数组进行寻址。因此,将这个问题归结为子字符串搜索算法。
使用稍加修改的Boyer搜索算法,您将获得更好的性能。把它想象成一种二维Boyer Moore搜索算法。
https://stackoverflow.com/questions/30672950
复制相似问题