To store N we can make a binary tree with extra data store is the no of left nodes in tree. now search cost is O(logN) and O(1) is the cost of finding no less than that particular no. also , we can update tree in O(logN) tIme.
On Sep 25, 6:16 am, Sticker <[EMAIL PROTECTED]> wrote: > I saw your ideas. Some of them are correct some are not. Here is what > I am thinking. > > >From the question we know that 1 ≤ M ≤ 1000000 and 1 ≤ N ≤ 4000. So > > notice that M >> N. Using a linked list to store M, you have to travel > it from either end, so at least M/2 travels each time, still larger > than N. So what if we keep M stored in an array(a simplest array > int[], called booArray) and do touch it. Rather we dynamically store > N? I use a linked list borLList to store all the borrowed books' > "original" position in booArray. > > Once we come across a borrowed index, we go through borLList, each > time a position smaller than the borrowed index, we increase the > borrowed index by one until we come across a position has a position > larger than it, then we insert this borrowed index to the current > position. Do another one and so on. > > Example: > 5 > 26 1 42 15 3 > 2 > 3 > 4 > > The booArray is 26, 1, 42, 15, 3, stored in booArray[1] to > booArray[5]. borLList is empty now. 3 is the first borrowed index, we > insert it into borLList and return booArray[3]. The next borrowed > index is 4, since the first element in borLList is 3, which is smaller > than 4, we increase this borrowed index by one, now it is 5, since no > larger element exists in borLList, we insert 5 into borLList and > return booArray[5]. Now the borLList is 3->5. > > As we can see, practically far less than 4000 times is required for > each borrowed index, which is definitely better than the double link > list solution (which is (S/2 -1) * (S/2 - 2) * (S/2 -3) * ... 1 as > given by jliang. > > I definitely do not agree the method to reorder the borrowed indexes. > This will give wrong answer. The order is important for this problem. > > I do not know how to use binary search tree to solve this problem, it > will be great if solution can be described here. > > On Sep 23, 12:17 pm, Jun <[EMAIL PROTECTED]> wrote: > > > 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 -~----------~----~----~----~------~----~------~--~---
