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

Question

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

Answer 1

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

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int main (){
    vector<int> items ;
    vector<int> 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<int> selectedItems;

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

    for(int i=0;i<notIncluded.size();i++){
        idx[notIncluded[i]] = false;
    }

    for(int i=0;i<items.size();i++){
        if(idx[i]){
            selectedItems.push_back(items[i]);
            cout << items[i] << " " ;
        }
    }

return 0;
}