0

我正在从向量中提取最小值。

说向量 = [0, inf, inf, inf];

ExtractSmallest(vector) = 0;

然后向量 = [0, 1, inf, inf];

但是现在，我们已经看到了 0。因此，

ExtractSmallest(vector) = 1;

我通过这样做在我的代码中表示这一点nodes.erase(nodes.begin() + smallestPosition);

但是，我现在意识到擦除是非常糟糕的。有没有办法在不擦除矢量的情况下实现这一点？只是跳过我们已经看过的那些？

Node* CGraph::ExtractSmallest(vector<Node*>& nodes)
{


    int size = nodes.size();
    if (size == 0) return NULL;
    int smallestPosition = 0;
    Node* smallest = nodes.at(0);


    for (int i=1; i<size; ++i)
    {

        Node* current = nodes.at(i);

        if (current->distanceFromStart <
            smallest->distanceFromStart)
        {
            smallest = current;
            smallestPosition = i;

        }
    }

    nodes.erase(nodes.begin() + smallestPosition);      


    return smallest;


}
4

1 回答 1

1

选项 1您可以有一个附加vector<bool>的并行迭代。bool当您找到最小元素时，将该向量中的位置标记为true。每当您进行迭代时，请跳过两个向量中标记为 的位置true。

选项 2如果顺序不重要，请保持到目前为止已删除的元素数量。当您找到最小值时，与第一个非排除元素交换位置。在新的迭代中，从第一个非排除元素开始。

选项 3如果顺序不重要，则对数组进行排序。（这需要O(n*log(n))）。现在将进行删除O(1)- 您只需排除第一个未排除的元素。

选项 4如果没有重复项，您可以将 a 保留std::set在包含所有排除元素的一侧。迭代时，检查当前元素是否已被排除。

于 2012-06-07T07:53:11.243 回答