Let's say i have a vector<int> datas = {10, 5, 6, 8 }

And a vector<int> index = {0, 2} (can be unsorted ex: {2,0} or {3,1,2})

The function needs to delete the datas at index 0 and 2 and keep the order.

So for this case i would get : result = { 5, 8 }

How is it possible to do this in Worst case Θ(n) ?

Every solution i try always have a nested loop which will be slower than Θ(n)..

Note : there's no duplicates and size of index vector is always <= size datas vector

Also i am trying to do this with basic for loops and indexing, no fancy c library stuff..

Any idea ? Thanks.

CodePudding user response：

You can do this better using more of the standard library, but here's a simple approach. It creates a bitmap of indexes in O(n) time, and then uses a standard trick of copying non-deleted elements down in the datas vector, finally resizing to remove the dead ones.

Here's a full example.

#include <iostream>
#include <vector>

void remove(const std::vector<int> &index, std::vector<int> &data) {
    auto b = std::vector<bool>(data.size());
    for (auto &i : index) {
        b[i] = true;
    }
    size_t n = 0;
    for (size_t i = 0; i < data.size();   i) {
        if (!b[i]) data[n  ] = data[i];
    }
    data.resize(n);
}

int main(int argc, char **argv) {
    std::vector<int> data = {10, 5, 6, 8};
    std::vector<int> index = {0, 2};
    remove(index, data);
    for (auto &i : data) {
        std::cout << i;
        std::cout << ", ";
    }
    std::cout << "\n";
}

CodePudding user response：

Also you can just 'flag' the data to be deleted in very simple loop. Just select a special number and call it a marker then modify the array and delete it later if matched. Ex.

int main()
{
    vector<int> a = {10, 5, 6, 8};
    vector<int> idx = {0, 2};

    for(int i=0; i < a.size(); i  ) {
        a[idx[i % idx.size()]] = 0xAFAF; //flag the data to be deleted
    }

    for(int i=0; i < a.size(); i  ) {
        if (a[i] == 0xAFAF) {
            a.erase(a.begin()   i);
        }
    }

    for(int i=0; i < a.size(); i  ) {
        std::cout << a[i] << std::endl;
    }
    return 0;
}

You also can use std::erase_if.