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

Question

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

问题是,有两个2d阵列,一个比另一个大.可以说,

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

和

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

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

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

Answer 1

我将使用空值（或 NaN）将较小的数组填充到较大的维度，转换为一维并截断/删除不必要的空值：

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

然后比较一维数组，同时跳过空值 - 这将是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)最好的情况（如果较大数组中的每个数字都不同）

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

我想你可以将数组转换为位置字典，并找出更复杂和更快的算法，如果你需要进行多次比较......

如果需要，您还可以旋转较小的数组，例如：

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