I can think of an o(n lg n) implementation that uses linked lists. Maintain LL of original book array: 26-> 1-> 42-> 15 ->3 this shrinks as books are removed. maintan LL of borrowed books: 3->4 .. Original LL now becomes 26->1->15
Sort the borrowed LL --(borrwored order may be 3->4->1 == 1->3->4) using borrowed LL reconstruct the missing books links in Original LL. (by inserting empty nodes in index positions from borrowed LL) Indranil can fill the gaps and find out which books were borrowed. Only sorting takes o(n lg n) rest are o(n)/o(1) operations. Let me know any comments of above approach. -MD On Sep 5, 8:34 am, adak <[EMAIL PROTECTED]> wrote: > Of course, the index numbers lower than the book being checked out, > don't need to be changed, just the higher numbers. > > I like using an array of structs with structure members which can > group all the relevant data together that I want for that book, or > student, etc. > > So Books[] might have: title, origLocation, (on the bookshelf), > borrower, etc. The original location number shouldn't be needed here, > but in practice, it's too important not to have it duplicated. > Especially while coding it up and testing. > > Linked lists can be substituted for arrays, if memory is a problem, of > course. The other list or array would have the original index number, > as the value in the current bookshelf number's element. > > Since the weak link in this type of organization of the program is so > striking (the index numbers), in practice, it would be preferred to > give each book it's own unique ID number, and forget the "places from > the left", routine. Obviously this is just an exercise with that as a > "monkey wrench", to be worked out, but it's worth keeping in mind for > RL programs. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
