我有一个 std 向量，其中每个元素描述 3D 空间中的一个点。因此每个点都有 X、Y 和 Z 坐标。现在的任务是遍历所有点，而不是找到与参考点距离最小的点，而是找到第二个或第三个最小距离的点。然后返回这个距离
我的问题是找到第 n 个最小距离的灵活实现。下面的代码用于一维空间，其中每个点都具有相同的位置以简化示例。
std::vector<double> point(10, 1.0);
double min_distance = 0.0;
for (int i = 0; i < point.size(); ++i)
{
for (int j = 0; j < point.size(); ++j)
{
if (i == j)
continue;
min_distance = std::min(min_distance, std::abs(point[j] - point[i]));
}
}
您可以使用该std::nth_element函数根据您的谓词对数组进行部分排序：
std::vector<double> points;
std::nth_element(points.begin(), points.begin() + n, points.end());
n你的第 n 个元素在哪里。如果您想获取所有劣于std::sort您的数组的元素并选择正确的元素。
的优点std::nth_element是，它可以是直链中的元素的数目，而std::sort是在O(nlogn)最坏的情况。
请注意，如果您使用std::nth_element，您的数组将不会被排序，但您只能保证您的第 n 个元素位于 position n。
编辑：使用自定义距离更新示例
Point reference;
std::vector<Point> points;
std::nth_element(points.begin(), points.begin() + n, points.end(),
[&reference](const Point& a, const Point& b) { return dist(reference, a) < dist(reference, b); });
或者您可以将比较器包装在一个结构中：
struct PointComp
{
Point reference;
bool operator<(const Point& a, const Point& b)
{
return dist(reference, a) < dist(reference, b);
}
};
PointComp comp; comp.reference = reference;
std::vector<Point> points;
std::nth_element(points.begin(), points.begin() + n, points.end(), comp);
如果您出于某种原因不喜欢 lambda。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句