I am agree with Sticker, I comes to write exactly what Sticker wrote. ;) It's O(N^2 / 2) that is 1+2+3+4+5+...+N.
On 9/25/07, 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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
