在2D数组中查找边界单元的快速方法 [英] Fast Way to Find Border Cells in a 2D array

问题描述

假设我有一个n x n 2D数组，其中的条目为0或1.例如:

Suppose that I have a n x n 2D array where the entries are either 0 or 1. For example:

[[0, 1, 1]
 [1, 0, 0]
 [0, 0, 0]]

现在，我想找到数组中1的相邻单元，它们是数组中1的侧面和对角线的直接对角线等于0的单元.因此，在上面的示例中，相邻单元为{(0，0)，(1，1)，(1，2)，(2，0)，(2，1)}.有一种执行此操作的蛮力方法，在该方法中，我遍历每个条目，如果它是1，则查看其邻居并检查其是否等于0.对于具有1s的高密度的大n，其数量为1.进行的检查约为8n ^ 2.但是，我觉得我可以利用此问题的冗余来提出更快的解决方案.例如，查看单元格(0，0)中的第一个条目后，我看到它具有两个相邻的单元格和一个相邻的0.因此，我知道我不必检查单元格(1，1)和它的邻居.我也知道在(0，1)和(1，0)处的条目是1，因此我可以将(0，0)添加为邻居单元格.

Now I want to find the neighbor cells of the 1s in the array, which are the cells to the sides and directly diagonal of the 1s in the array that equal to 0. So in the example above, the neighbor cells would be {(0, 0), (1, 1), (1, 2), (2, 0), (2, 1)}. There is the brute-force method of doing this, where I iterate through every entry and if it is a 1, I look at its neighbors and check if it equal to 0. For large n with a high density of 1s, the number of checks made is around 8n^2. However, I feel like I can make use of the redundancy of this problem to come up with a faster solution. For example, after look at the first entry in the cell (0, 0), I see that that it has two neighboring ones and a neighboring 0. So I know that I don't have to check the cell (1, 1) and its neighbors. I also know that at (0, 1) and (1, 0) the entry is 1, so I can add (0, 0) as a neighbor cell.

有人可以针对这个问题提出的最快解决方案是什么?就个人而言，我正在考虑使用某种BFS或DFS实现，但是我不确定如何实现它.我当时在考虑只需要大约n ^ 2张支票，而不是大约8n ^ 2张支票.

What's the fastest implementation of a solution to this problem that someone can come up with for this problem? Personally, I've thinking of using some sort of BFS or DFS implementation, but I'm not sure how I would implement it. I was thinking instead of taking around 8n^2 checks, it would only take around n^2 checks.

(另外，我不知道这是否是leetcode问题.看起来像是一个leetcode问题，所以如果有人在leetcode上知道此问题的名称或编号，请告诉我！)

(Also, I don't know if this is a leetcode problem. It seem suitable to be one, so if anyone knows the name or number of this problem on leetcode, please let me know!)

推荐答案

好吧，我想到了一个降低 8 的想法.

Well, I can think of an idea that will lower the 8.

首先，您将矩阵中的所有数字相加，这将为您提供矩阵中有多少个1.可以在 O(n ^ 2)中进行此步骤.

First you sum all the numbers int the matrix, that will gives you how many 1s there are in the matrix. This step can be made in O(n^2).

然后，如果小于1的小于(n * n)/2 ，则以1进行检查.我的意思是，每一项都用，如果为1，则在八个邻居中寻找所有0职位(并将它们添加到答案中).

Then if there are less 1s than (n * n) / 2 you do the check by the 1s. I mean you go for every item and if it is a 1 you look for all the 0 positions in the eight neighbor (and add them to your answer).

在另一面，如果1大于(n * n)/2 ，则您执行相同操作，但是这次以0进行校验.你去寻找每一项，如果它是0，则在八个邻居中寻找至少一个1.如果有1个邻居，则将当前0个位置添加到答案中.

In the other side, if there are more 1s than (n * n) / 2 you do the same but this time you do the check by the 0s. You go for every item and if it is a 0 you look for at least one 1 in the eight neighbor. If there is a 1 neighbor you add to your answer the current 0 position.

为什么要这样做?好吧，您最多要检查8个邻居(n ^ 2)/2 ，因此最坏情况下的最终时间将是: n ^ 2 + n ^ 2 + 8(n ^ 2)/2 = 2n ^ 2 + 4(n ^ 2) = 6n ^ 2

Why doing this? Well you are checking the 8 neighbor at most (n^2)/2 so the final time in the worst case will be: n^2 + n^2 + 8(n^2)/2 = 2n^2 + 4(n^2) = 6n^2

Ps:感谢@unlut指出了此答案的一些错误

Ps: Thanks to @unlut that pointed some error this answer had

这篇关于在2D数组中查找边界单元的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！