查找何種順序原創要素，從一個陣列

Question

刪除我有以下任務的一個問題：

在你開始用正數的數組，從1到n的開始。然後通過選擇當前數組中的索引來逐個刪除條目。 我將輸出原始元素被刪除的順序。

例如：

輸入：

6 

1 4 4 2 2 1 

輸出：

1 5 6 3 4 2 

速度是很重要的，所以我需要的解決方案是儘可能快。看起來它可以做得很少 - 哦（n^2），但我不知道如何。解決方案必須是C++。

我是正確的，儘管速度太慢解決方案：

int n = 0; 
std::cin >> n; 

std::vector<int> nums(n); 
std::iota(nums.begin(), nums.end()); 

for (int i = 0; i < n; ++i) { 
    int toRemove; 
    std::cin >> toRemove; 
    --toRemove; 
    std::cout << nums[toRemove] << " "; 
    nums.erase(nums.begin() + toRemove); 
} 

Answer 1

如果你可以改變從vector您的容器類型的list那麼你可不必每次複製元素，你刪除一個。這應該會更有效率，但是查找的複雜性增加使這個解決方案陷入困境，除非在幾乎最佳的情況下，這種改進太大無法改進。

#include <vector> 
#include <list> 
#include <iostream> 
#include <numeric> 
#include <iterator> 

template<typename T, template <typename, typename> class Container> 
class LookupRemove { 
    typedef Container<T, std::allocator<T> > ContainerType; 
public: 
    LookupRemove(int size): 
    remaining(size), 
    nums(size) { 
    std::iota(nums.begin(), nums.end(), 1); 
    } 

    T removePosition(T position) { 
    if (position < remaining) { // make sure advance doesn't go past end 
     auto pos = nums.begin(); 
     std::advance(pos, position); // set the position to retrieve and remove 
     T value = *pos; 
     nums.erase(pos); 
     --remaining; 
     return value; 
    } 
    return 0; 
    } 
private: 
    ContainerType nums; 
    T remaining; 
}; 

int main() { 
    int n = 1000000; 

    LookupRemove<int, std::vector> lookupVector(n); 
    for (int i = 0; i < n; ++i) { 
    lookupVector.removePosition(0); 
    } 

    LookupRemove<int, std::list> lookupList(n); 
    for (int i = 0; i < n; ++i) { 
    lookupList.removePosition(0); 
    } 
    return 0; 
} 

一些時間譜測量：

elements: 10000 
vector:  5.0 ms 
list:   - ms 

elements: 100000 
vector:  639.0 ms 
list:   1.0 ms 

elements: 1000000 
vector: 83022.0 ms 
list:  25.0 ms 

編輯：此分析是有缺陷的，因爲它是從列表中刪除，每次取出第一個成員的最佳案例。使用隨機位置進行分析顯示，從矢量中刪除與從列表中刪除的時間相當。