arrays - 在一组树中找到正方形

Question

假设我们是一个有 N 棵树的森林里的猎人。为了猎取最好的鹿，我们打算在一棵树到另一棵树之间 build 栅栏，这样我们最终就能得到一个精确的正方形。进一步假设我们得到了森林中 N 棵树中每棵树的 (x,y) 坐标列表。我们想找到最大可能的正方形以及任意大小的可能正方形的总数？以 O(N^2) 为目标。

例如列表 (4, 10), (3, 13), (2, 10), (1, 13), (3, 11), (5, 11), (4, 14), (1, 11), (9, 15), (9, 11), (5, 15) 包含三个可能的正方形，这三个正方形中最大的正方形由 (5, 11), (9, 15), ( 9, 11), (5, 15).

---

我的基本尝试是编写一个遍历整个点列表(从 1 到 N)的 for 循环，然后包含第二个 for 循环再次遍历所有点，从 i 到 N，其中 i是第一个 for 循环的当前增量。现在这两点唯一确定剩下的两点。因此，我们还需要一个 for 循环(从 j 开始，其中 j 是第二个 for 循环的当前增量)来检查这两个剩余点是否存在。如果它们存在，那么我们就找到了一个正方形。找到所有正方形后，找到最大的正方形就很简单了。

但是，这个想法需要三个 for 循环，即 O(N^3)。所以我想知道如何优化此代码以实现 O(N^2)。

Answer 1

These two points now uniquely determine the remaining two points.

您的想法是正确的:遍历每一边，并尝试围绕它构建两个正方形(一个正方形将是另一个正方形的镜像)。

However, this idea requires three for-loops, i.e. O(N^3). So I am wondering how one could optimise this code to achieve O(N^2).

您可以将第三个循环替换为哈希表查找，其复杂度为 O(1)。构建哈希表需要 O(N)，因此您的算法的总体时间将为 O(N^2)。