I already know how to solve it. Binary Index Tree is good approach to solve this problem. Thanks very body involved in this discussion!
On Sep 22, 6:31 am, KK <[EMAIL PROTECTED]> wrote: > On Sep 5, 11:07 am, jliang <[EMAIL PROTECTED]> wrote: > > > how about a doubled linked list where you can remove item at any > > index. the removing is O(1). you can also keep track of the current > > removing from a doubled linked list is O(1)? How? > > > size S so if you are borrowing book at index greater than S/2, you > > traverse the list from the end, if index < S/2, you traverse from the > > beginning. > > > every time a book is removed, S becomes 1 smaller, so the traversal > > time is something like (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 > > > you can also put them in a binary tree, so every operation is O(lgN) > > putting the original array in binary tree takes O(M lgM) time, and you > will lose the original indices. So it's of no use. > > > so the total will be O(lgN M) > > I dont think so. correct me if I am wrong. --~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
