mardi 14 juillet 2020

Is there an efficient method to remove elements from a sorted vector in order?

Consider a sorted list of numbers A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} from where one element will be eliminated at each step.

Suppose, I remove A[4] item, we have A = {0, 1, 2, 3, 5, 6, 7, 8, 9}.
Then I remove A[4] item again, we have A = {0, 1, 2, 3, 6, 7, 8, 9}
Then A[7] item, we have A = {0, 1, 2, 3, 6, 7, 8} and so on.

Consider that we know the indices of the elements to be removed in each kth array beforehand i.e 4, 4, 7,...
If I were to implement this in C++ and A was a std::vector, I would need to call A.erase(A.begin()+k) each time and we will have an algorithm that runs in O(n^2). I cannot even use std::remove here as elements do not repeat.

What would be the most efficient approach here?

Aucun commentaire:

Enregistrer un commentaire