On Fri, Dec 20, 2013 at 07:01:17PM -0800, Ali Çehreli wrote:
> 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).
[...]
If you know the which elements you're going to remove, you can remove
them all at once in O(N) time:
int[] arr = [ ... ];
for (i=0, j=0; i < arr.length; i++)
{
if (deleteThisElement(arr[i]))
continue;
if (j < i)
arr[j] = arr[i];
j++;
}
arr.length = j;
Of course, if you know which *indices* you're going to remove, then you
can do even better (by starting your loop at the first index to be
deleted).
T
--
BREAKFAST.COM halted...Cereal Port Not Responding. -- YHL
