1

我得到一个包含 4 个未排序元素的向量，该向量如下所示：

vector<positionInfo> objects

其中 positionInfo 是一个结构：

struct positionInfo
{
  int X_pos;
  int Y_pos;
}

现在，这 4 个元素没有排序，但我希望它们按特定顺序排列，即：

  • 元素 1 ( [0] ) 必须具有最低的 Y 和 X 位置。
  • 元素 2 ( [1] ) 必须具有最高的 X 位置但最低的 Y 位置。
  • 元素 3 ( [2] ) 必须具有最高的 Y 和 X 位置。
  • 元素 4 ( [3] ) 必须具有最低的 X 位置但最高的 Y 位置。

这只是为了轻松访问形成立方体的 4 个点中的任何一个，使用大量变量可能会得到我想要的，但我认为这并不是真正的最佳选择，是否有任何算法可以用来减小代码的大小并提高速度？

4

3 回答 3

2

如果您完全确定自己有解决方案，则可以部分使用std::sort.

例如（3 个步骤）：

重载<运算符：

bool
operator < (const positionInfo & left, const positionInfo & right)
{
    return left.X + left.Y < right.X + right.Y;
}

接下来，对向量进行排序：

std::sort( &objects[0], &objects[4] );

请注意，在此示例中，向量正好有 4 个元素。

结果，您将获得一个向量，其中第一个和最后一个元素根据您的意愿进行排序。

最后一步 - 如果需要，交换内部元素：

if ( objects[1].X < objects[2].X )
    std::swap( &objects[1], &objects[2] );

完毕。

于 2013-06-09T09:40:14.387 回答
0

您的条件不是数据的本地条件。如果一个元素大于或小于另一个元素，您应该有关于所有要计算的元素的信息。

我将用图像来说明这一点：

在此处输入图像描述

仅考虑 (1) 和 (2) 或 (3) 和 (4) 不可能说什么应该更大：

如果 (1) 和 (2) 的y坐标大于 (3) 和 (4)，它们将交换位置。

但是，通常的搜索算法仅在假设您可以在本地比较元素时起作用，因此您可以决定两个元素中的哪一个更大，只考虑 2 个元素。

所以你不能使用标准的排序算法。

相反，您应该创建新向量并根据条件用元素填充它：

new_objects[0] = find_elememt_with_lowet_x_and_y(objects);
new_objects[1] = find_element_with_highets_x_and_lowest_y(objects); 
//....
objects = new_objects;
于 2013-06-09T08:48:04.113 回答
0

几点：

  • 四个点不形成一个立方体 - 它有 8 个顶点。如果您的意思是确定一个立方体，您可能需要 3 个维度。我假设你说的是正方形
  • 如果您实际上不是在处理正方形，而是使用随机的 4 个点，则您的排序不清楚 -Element 1 ( [0] ) must have the lowest Y and X pos例如，它不需要最低y且x在同一点。

但是，如果您的意思是正方形，而不是立方体，并且确实确定要处理这种情况，则可以通过以下方式进行

  • 循环所有四个顶点
  • 找到最小和最大x和ys
  • 因为您确定您要处理的情况，您可以从这 4 个值中创建 4 个兴趣点。
于 2013-06-09T08:50:57.480 回答