0

ベクトルから最小値を抽出しています。

ベクトル=[0、inf、inf、inf];と言います。

ExtractSmallest(vector) = 0;

次に、vector = [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

オプション1vector<bool>並行して反復する追加機能を使用できます。最小の要素を見つけたら、boolベクトル内のその位置を。としてマークしtrueます。繰り返すときはいつでも、としてマークされている両方のベクトルの位置をスキップしてくださいtrue。

オプション2順序が重要でない場合は、これまでに削除された要素の数を維持します。最小値を見つけたら、除外されていない最初の要素と位置を入れ替えます。新しい反復では、除外されていない最初の要素から開始します。

オプション3順序が重要でない場合は、配列を並べ替えます。（これにはかかりますO(n*log(n))）。削除が必要になりますO(1)-除外されていない最初の要素を除外するだけです。

オプション4std::set重複がない場合は、この時点までに除外されたすべての要素をそのままにしておくことができます。繰り返すときは、現在の要素がすでに除外されているかどうかを確認してください。

于 2012-06-07T07:53:11.243 に答える