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 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) so the total will be O(lgN M) On Sep 5, 2:53 am, Ray <[EMAIL PROTECTED]> wrote: > I know the naive method. It's very straight. Just maintain an index > array which records the > > index of the books. whenever one book is removed then update all > elements in the index array after its index. > > It runs O (M N). I'd like to know is there any efficent data structure > to speedup it? > > Thanks. > > On Sep 5, 10:14 am, Ray <[EMAIL PROTECTED]> wrote: > > > He has lost many books, since many of his friends borrow his books and > > never bother to return them. He does not want to lose any more books > > and has decided to keep a record of all books that he lends to his > > friends. To make the task of borrowing a book a little difficult, he > > has given the following instructions to his friends: when they borrow > > a book, they must record in a register its position from the left > > among the books currently on the shelf. > > > Suppose there are 5 books in the library and they are arranged as > > follows: > > > 26 1 42 15 3 > > If someone walks in and borrows the book 42, then he will record 3 in > > the register because this book is the third from the left on the > > shelf. Now the shelf looks like this: > > > 26 1 15 3 > > If the next person borrow the book 3, he writes down 4 in the register > > since this is currently the fourth book from the left on the shelf, > > and so on. > > > Indraneel knows the initial arrangement of the books in his library at > > the time that he introduced the register system. After a while he > > examines his register and would like to know which books have been > > borrowed. Your task is to write a program to help Indraneel solve this > > problem. > > > Input format > > > The first line of the input contains a single integer M indicating the > > number of books in Indraneel's library. The next line contains M > > distinct positive integers describing the sequence in which the books > > are arranged on the library shelf. The third line of input contains a > > single integer N indicating the number of entries in the register. > > This, in turn, is followed by N lines (lines 4 to N+3), each > > containing one positive integer. The integer on line 3+i indicates the > > position from left of the book ith book borrowed. (You may assume that > > the number on line 3+i is at most M-i+1.) > > > Output format > > > N lines with one positive integer on each line. The number on line i > > is the book borrowed by the ith borrower. > > > Test Data: > > > You may assume that 1 ≤ M ≤ 1000000 and 1 ≤ N ≤ 4000. > > > Example: > > > Here is the sample input and output corresponding to the example > > discussed above. > > > Sample Input > > > 5 > > 26 1 42 15 3 > > 2 > > 3 > > 4 > > Sample Output > > > 42 > > 3 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
