提取矢量的最小值

說vector = [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; 


}

來源

2012-06-07 CyberShot

選項1你可以有你在並行迭代的額外vector<bool>。當您找到最小的元素時，將bool向量中的該位置標記爲true。無論何時迭代，都跳過標記爲true的兩個向量中的位置。

選項2如果順序不重要，請保留迄今刪除的元素數量。當您找到第一個未排除元素的最小交換位置時。在新的迭代中，從第一個未排除的元素開始。如果訂單不重要，請對數組進行排序。（這需要O(n*log(n))）。刪除現在需要O(1) - 您只需排除第一個未排除的元素。

選項4如果沒有重複項，您可以保留一個std::set與所有排除元素一側到這一點。迭代時，檢查當前元素是否已被排除。

來源

2012-06-07 07:53:11

提取矢量的最小值

回答

相關問題