Removing multiple elements from array

[Ali Çehreli]

On 12/20/2013 06:17 PM, aldanor wrote:
> On Saturday, 21 December 2013 at 01:42:04 UTC, Ali Çehreli wrote:
>
>> That's probably a bug, right? The indexes would probably become off as
>> the array gets shorter.
>
> Note the .reverse there?

Yes, I missed that part. :)

> Which makes sure indices don't get off. Still,
> that's probably an inefficient way of doing this...

Yeah, every removal would move the right-hand elements one position to 
the left. But you would be removing only M times (the number of 
indexes). So the complexity is I think O(M logM) + O(NM) for sorting the 
indexing plus removing M elements by shifting at the order of N elements.

The range solution that I've come up with is I think O(M log M) + O(M) + 
O(N), for sorting the indexes, removing the duplicates with uniq and 
iterating the elements. Since O(M log M) dominates O(M), it should be 
O(M log M) + O(N).

Ali

P.S. Hm. I think I've reading an algorithms book lately. :p