在二进制矩阵中找到最大的X形状

Question

在二进制矩阵中找到最大的X形状

5

我最近参加了一家公司的技术测试，他们提出了一个非常有趣的问题，即如何在二进制矩阵中识别形状。

练习的目标是创建一个算法，能够找到二进制矩阵中最大的X形状，并返回其长度。X的定义如下： - X由两条长度相等的对角线组成，它们共享一个唯一的点。例如：

101
010
101

包含3个有效字符的X，因此算法将返回3。

没有包含任何有效的 X，因此算法将返回1，因为长度为1的X是单个1。

我已经完成了这个练习，但是我实现了一个非常混乱的算法，时间复杂度估计为O(n3)，对于非常大的矩阵来说是不好的且不适用。这种复杂性的很大一部分是我用来遍历矩阵的双重循环造成的。

我该如何编写更简洁的算法呢？我提出这个问题是出于个人兴趣，并需要改进我的技能和实际思考能力。

- Le_Ruf

1

X需要用零“勾勒”吗？或者（例如）全为1的数组是否被认为具有跨越整个网格的X？ - ruakh

@ruakh 它不需要被0勾勒出来。只要满足两个对角线共享一个唯一点的条件即可。 - Le_Ruf

顺便说一句，我认为最干净的算法是O(n^3)。不要混淆“凌乱”和“慢”！ - ruakh

我实际上经历了几次迭代，而我的当前迭代速度更快，我相信！长话短说，我检查数组中的每个元素，并且当我找到一个1时，我尝试检查它的对角线可以延伸多少来寻找可能的最大X。 - Le_Ruf

如果没有“轮廓”要求，那么“对角线相等”是什么意思呢？（因为现在可能有一条比另一条长）。 - Henry

1

等对角线要求意味着两条对角线长度相同，并共享一个唯一的1。我编辑了第一篇帖子以使其更清晰！ - Le_Ruf

4个回答

1

虽然问题没有明确指定，但我假设两条对角线的共同点必须位于中心以形成有效的“X”形。图片似乎支持这个假设。

想象一下，数组被旋转了45度，现在我们正在寻找与x和y轴对齐的十字架。

您可以逐行检查连续的1。只有一个奇数个1的跨度才可能是十字架的一部分（否则就没有中间元素）。

对于每个这样的跨度，请检查是否真的有一个十字架。

如果我们只对最大尺寸感兴趣，那么如果跨度比迄今为止发现的最大值短或相等，则可以省略交叉检查。

识别水平跨度所需的时间为O（n ^ 2）。对于长度为m的每个水平跨度，您在另一个方向上最多检查m + 2个元素。所有跨度长度的总和显然为O（n ^ 2），因此进行十字检查所需的时间也为O（n ^ 2）。

因此，该算法的总工作量为O（n ^ 2），不需要额外的空间。

- Henry

只有一个包含奇数个1的跨度才可能成为十字形的一部分（否则就没有中间元素）。这里X的定义似乎不需要对角线在中间相遇，只需要在一个公共点相遇即可。这可能值得在问题或您的答案中澄清。 - Patrick87

@Patrick87，你是对的，重新阅读问题的确切措辞似乎也允许“V”形状。我会添加一条备注。 - Henry

我同意，测试中没有明确说明，所以我不确定它是否也应该允许不均匀的X。这个问题并不是很清楚。 - Le_Ruf

1

这是一个时间复杂度为 O(m*n) 的过程，其中 m 是行数，n 是列数：

从上到下逐行迭代。每个 1 可以有零到两个父级。如果 1 有父级，则将其分配给其父级的父级。保存具有两个父级的单元格。现在对“子级”执行相同操作，从下到上遍历行。之后，找到具有两个父级和两个子级的单元格，显示最大大小的 X。

自上而下：

p1   ...   p2
  p1 ... p2
   [p1,p2] // one cell with two parents
...
...

从下到上：

...
...
   [c1,c2]
  c1 ... c2
c1   ...   c2

- גלעד ברקן

0

O(n) 空间和 O(n) 时间（n 为单元格数）：

在 O(n) 时间内，将矩阵的每个元素与沿着“1”单元格的 NE、SE、SW 和 NW 直线的最大距离相关联（像地图一样读取矩阵）。
在 O(n) 时间内，找到既是“1”又具有这四个值中最大最小值的单元格。您可以同时完成设置这四个值的最后一个操作。
最大长度比上述最大最小值的两倍多一。

- Dave

为了说明为什么步骤1是O(n)：假设我们想要填充SE值。矩阵的S和E两侧的每个单元格都具有SE_val = 0，然后从S和E边缘一行/列一个接着一个地进入，每个单元格要么得到SE_val = 0（如果SE单元格为0），要么得到SE_val = 1 + SE单元格的SE_val。这会按每个方向一次查看每个单元格。这可以进一步优化，但仍将是O(n)。 - Dave

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ruakh · Accepted Answer

如果您可以接受O（n ^ 2）的额外空间，那么一种选择是构建两个额外的数组：一个记录以每个单元格为中心的最长“\”形状的长度，一个记录最长“/”的长度。（您可以使用三重嵌套循环在O（n ^ 2）时间内构建每个数组 - 这听起来可能像O（n ^ 3）时间，但记忆化意味着您只需要对给定的“\”或“/”迭代一次，因此内部循环可以实现摊销常数时间。）然后您遍历所有位置;对于任何位置，位于该位置的最大X的大小等于两个矩阵在该位置的较小值。只需跟踪最大的较小值即可完成。

这具有最坏情况下的时间复杂度为O（n ^ 2），显然是渐近最优的。