c++.de :: remove a set of values in an array given a set of indexes

Unregistrierter

Hi,

what is the best way to remove a set of values in an array? The set of values to remove is given as an array of indexes.
I can think of several solutions, either O(n) or O(n logn) with different memory requirements
array = [12, 24, 50, 1, 4, 5, 6, 9, 24, 6, 7, 3, 23, 2];
Index_to_remove = [4, 2, 1, 13, 9, 6];

cooky451 Mitglied 18:26:52 03.01.2013 Titel:

If the order isn't fixed the fastest variant is probably to just swap the values to the end and than cut them off.

Michael E. Mitglied 18:51:14 03.01.2013 Titel:

Do you have to keep the order? If yes, then cooky's method does not work. But how can you calculate the result in linear time?

Edit: Sorry, cooky, should've read your whole post.

camper Mitglied 19:02:44 03.01.2013 Titel:

cooky451 schrieb:

If the order isn't fixed the fastest variant is probably to just swap the values to the end and than cut them off.

That works only if values located at the end are known to be kept.

Unregistrierter 19:08:21 03.01.2013 Titel:

Can you use special values in array to mark elements for removal (such as negative numbers, NaN, ...)? This way O(n) without additional memory would work.

cooky451 Mitglied 19:18:08 03.01.2013 Titel:

Guys.. he doesn't have values, he already has the index of the elements.

Unregistrierter 19:29:16 03.01.2013 Titel:

I know.

knivil Mitglied 21:37:12 03.01.2013 Titel:

cooky451 schrieb:

Guys.. he doesn't have values, he already has the index of the elements.

Maybe you can use unused bits in your "number".

cooky451 Mitglied 21:46:55 03.01.2013 Titel:

..what?

Unregistrierter 21:50:17 03.01.2013 Titel:

eg. bit 31 is never set because the input range (of array) is limited. So you can loop through Index_to_remove, set bit 31 for every index in array, then loop through array and remove the values with bit 31 set...