Another approach will be to insert the elements in order and remove the first(or the second) half in operation 2 Another approach would be to use a bitset , just mark all the elements in the specific range as 0 . We are not supposed to retrieve the elements so , keep a bit corresponding to every element (has the number , find it's position and put it there , a simple one one mapping will do) Now , just mark all top elements as false on the second go . PS:Would come up with the proof for amortized complexity soon , but can be done something like this
First operation O(1) , second operation O(n) .However , we can only insert or delete , from this sequence of n items , in O(n) time in the worst case . These operations can be completed in a sequence in O(n) time . So the amortized complexity should be O(n)/n or O(1) . On Jan 30, 3:44 pm, juver++ <avpostni...@gmail.com> wrote: > 1. Add element to the end of the array. > 2. Find median of the array, and partion the array into two sets, the second > one (where element >= median) is removed. > > At each operation 2, array's size decreasing by factor 0.5. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
