给定一个不能复制的索引列表,将元素从向量复制到另一个元素的最有效方法

假设我有一个向量V = {5, 10, 2, 1, 6}和一个list of indices= {2, 3, 0}.现在,生成的数据结构U应该包含{10, 6}不一定按顺序排列的元素.天真的方法将具有时间复杂性O(n^2).我们可以更好吗？

你可以添加一个矢量大小的bool数组来指示是否采用这个索引,在O(n)中填充这个数组然后你可以遍历vector并选择另一个O(n)中的元素O(2*n)= O(n),如下所示:

#include 
#include 
#include 
using namespace std;

int main (){
    vector items ;
    vector notIncluded ;
    items.push_back(1);
    items.push_back(2);
    items.push_back(3);
    items.push_back(5);
    notIncluded.push_back(1);
    notIncluded.push_back(0);

    vector selectedItems;

    bool idx[items.size()];
    memset(idx, true, sizeof(idx));

    for(int i=0;i