CODEWITHSUNDEEP
c++arrayslistvectorstl
Gyanshu
Gyanshu

Reputation: 199

Most efficient way to copy elements from a vector to another, given a list of indices which are not to be copied

Let's say i have a vector V = {5, 10, 2, 1, 6} and a list of indices= {2, 3, 0}. Now the resulting data structure U should contain the elements {10, 6} not necessarily in order. The naive approach will have a time complexity of O(n^2). Can we better that?

Upvotes: 2

Views: 1325

Answers (2)

mina sameh
mina sameh

Reputation: 1069

you can add a bool array of the vector size to indicate whether this index will be taken or not, filling this array in O(n) and then you can loop over the vector and select the elements in another O(n) that will be O(2*n) = O(n), like the following:

#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;
}

Upvotes: 6

skag
skag

Reputation: 180

We can do in O(nlog(n)) by sorting the list of indices then selecting the elements from vector whose indices are not in the sorted list. Sorting will take O(nlog(n)) and going through vector would be O(n)

O(nlog(n))+O(n)=O(nlog(n))

Upvotes: 0

Related Questions