c++ - 高效的数据结构，可进行稀疏数据查找

情况:

给定一些坐标为(x，y)的点
范围0
我必须找到最小的正方形，该正方形的边缘和内部至少包含N个点。

我使用 vector 存储坐标，并搜索了边长为minLength到边长为maxLength的所有正方形(在相关空间中应用蛮力)

struct Point
{
        int x;
        int y;
};

vector<Point> P;
int minLength = sqrt(N) - 1;
int maxLength = 0;

//   bigx= largest x coordinate of any point
//   bigy= largest y coordinate of any point
//   smallx= smallest x coordinate of any point
//   smally= smallest y coordinate of any point

(bigx - smallx) < (bigy - smally) ? maxLength = (bigx - smallx) : maxLength = (bigy - smally);

对于我抬起的每个正方形，遍历完整的 vector 以查看其边缘和内部是否至少有N个点。

这是相当低效的时间。

Q1。在不更改所使用算法的情况下，应使用哪种数据结构来提高时间效率？
Q2。这个问题的高效算法？

最佳答案

在2个相对的边缘上有点-如果没有，则可以将正方形缩小1并仍然包含相同数量的点。这意味着边缘的可能坐标限于输入点的坐标。但是，输入点可能不在角落。 (对于最小矩形，在所有4条边上都会有点，因为您可以缩小一个尺寸而不会改变另一个尺寸)

接下来要实现的是，每个点将平面划分为4个象限，每个象限包含多个点。 (由于象限有一个像素重叠，所以这些点的总和可能超过点的总数)。假设NW(p)是指向p点西北的点数，即具有x>=px and y>=py的点数。那么一个正方形中的点数就是NW(bottomleft) + NW(topright) - NW(bottomright) - NW(topleft)。

计算所有输入点的NW(p)相当容易。通过x对它们进行排序，并通过x对相等的y进行排序。最西北的点具有NW(p)==0。如果下一个点在第一个点的东南方，则可以使用NW(p)==1，否则可以使用NW(p)==0。在此阶段跟踪SW(p)也是很有用的，因为您正在研究从西到东的点，因此它们没有从北到南排序。计算出NW(p)后，您可以确定O(1)中正方形S的点数

回想一下，正方形大小受在相对边缘上具有点的限制。假设这些点位于左侧(西边)和右侧边缘-您仍然可以按x顺序对这些点进行排序。首先假设左边缘在您的最左x坐标处，然后查看右边缘必须包含N个点。现在，将左边缘移动到下一个x坐标，并找到一个新的右边缘(从而找到一个新的正方形)。这样做直到正方形的右边缘是最右边的点。

正方形在y方向上受约束也是可能的。只需沿y方向对点进行排序并重复，然后在两个结果之间选择最小的平方即可。

由于您是线性遍历x和y方向上的点，因此该部分只是O(N)，而主导因素是O(N log N)排序。

关于c++ - 高效的数据结构，可进行稀疏数据查找，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24402312/