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
